leetcode/CombinationSum2 -- zjuwangk at master · cgwy/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//2014-8-19
class Solution {
private:
	vector<int> path;
	vector<vector<int>> resVec;
	int target;
	void DFS(vector<int>& cand, int raw_start)
	{
		for(int i=raw_start;i<cand.size();i++)
		{
			if(raw_start == 0)
			{
				int x=1;
				x++;
			}
			if(cand[i] > target)
				return;
			else
			{
				int start = i;
				while(i+1 < cand.size() && cand[i+1]==cand[start])
					i++;
				int j;
				for(j=start;j<=i;j++)
				{
					path.push_back(cand[j]);
					target -= cand[j];
					if(target > 0)
						DFS(cand, i+1);
					else
					{
						if(target == 0)
							resVec.push_back(path);
						j++;
						break;
					}
				}
				j--;
				for(;j>=start;j--)
				{
					target += cand[j];
					path.pop_back();
				}
			}
		}
	}
public:
    vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
		//remove dupliucated from candidates;
		sort(candidates.begin(), candidates.end());
		this->target = target;

		DFS(candidates, 0);
		return this->resVec;
    }
};