leetcode - 40. Combination Sum II

40. Combination Sum II

Given acollection of candidate numbers (C) and a target number (T),find all unique combinations in C where the candidatenumbers sums to T.

Each number in C mayonly be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example,given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 

  [1, 7],

  [1, 2, 5],

  [2, 6],

  [1, 1, 6]

       这一题和上一题有些不同，上一题是在数组里的元素可以多次使用，这一题就不可以了。

给定一个数组，然后再给定一个target的值，选择数组中的若干个元素的值求和，使得这个和的值等于target，然后记录下这些元素并返回。

PS：每个元素可只可以使用一次，并且相同的元素组合只需记录一次，如[1,2,3]和[3,2,1]等价，只需返回[1,2,3]。

算法思想

         可以采用深度优先遍历(dfs)，考虑优化dfs，也就是剪枝，大大加快了算法的速度。

因为查找几个元素是否满足和等于target，至少就需要二重遍历，所以复杂度是大于O(n)的，那么可以考虑先将数组排序，再进行dfs，利用vector模拟栈操作。

步骤

1．  初始化当前和记为s，当前栈为v。

2．  若s等于target，则把v中的所有元素记录，并回溯。

3．  若s不等于targe，从上个元素下标后一位开始遍历数组，更新s的值，新的s的值等于旧的s值加上当前遍历到的元素：

a)        若新的s值大于target的值，回溯，s值等于旧的s。//剪枝

b)        若新的s值小于等于target的值，就跳到2。//dfs

class Solution {

private :
    int s;
    vector<int> v;
    vector< vector<int> >result;
    
public:

void dfs(vector<int> ca,int target , int now){
    	int before_check = -1;
	if(s == target){
		result.push_back(v);
		return;
	}
	
	for(int i = now ; i < ca.size() ; i++){
	    if(before_check == ca[i])continue;
	    before_check = ca[i];
		if(s + ca[i] <= target){ // if <= target
			v.push_back(ca[i]);
			s += ca[i];		
			dfs(ca,target,i+1);//从上个元素下标后一位开始dfs
			s -= v.back();
			v.pop_back();
		//	cout << endl << "       ret        "<<endl;
		}
		else{
			return;
		}
	}//for(i)
	
}
    
vector<vector<int>> combinationSum2(vector<int>& ca, int target) {
    sort(ca.begin(),ca.end());
    int before_check = -1;
	for(int i = 0; i < ca.size() ; i++){
		s = 0;
		if(before_check == ca[i])continue;//
		before_check = ca[i];
		s += ca[i];
		v.push_back(ca[i]);
	    dfs(ca,target,i+1);
	    v.pop_back();
	}//for(i)
	return result;
}  
};