Combination Sum

Description:

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

The same repeated number may be chosen from C unlimited number of
times.

Notice:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

Example:

given candidate set 2,3,6,7 and target 7, A solution set is:

[
    [7],
    [2, 2, 3]
]

分析：

   这道题和Combination Sum II基本相似，唯一不同的是，同一个数字可以无限次的使用。所以对于这道题，问题的重点就在于： 对于A的某一个值A[n]，紧接着的下一步搜索是否还要考虑它。

  • 如果紧接着的下一步搜索还要考虑它，就另紧接着的搜索起始点还为当前的起始点 n 。
  • 如果紧接着的下一步搜索不再考虑它，就另紧接着的搜索起始点为 n+1 ，此时直接考虑下一个值。

   而在Combination Sum II中，当搜索深度（即搜索起始点）为n时，不论是否加上当前值，接下来的搜索起始点都是n+1 ，直接考虑下一个值。

   如果把整个搜索过程当作一个多叉树的遍历，过程如下：

   其中可以把它抽象成一个二叉树：对每一个节点只有两个孩子，左边是加上它，右边（用圆圈圈住的）是不加上它。

思路：

   和Combination Sum II基本相似，只是多了一步：当搜索到A[n]时，紧接着的下一步搜索是否还要考虑它。

   最主要的是如果考虑它，什么时候不再考虑它，有点绕，比如 A[0]=1 ，target=4 ，如果接下来的每一步还要考虑它，并假设 sum=A[0]+A[0]+A[0]+A[0] ，此时已满足 sum=target ，下一步 sum + A[0] = 5 > target ，很明显此时就应该不再考虑它。所以是否接着的下一步搜索是否还要考虑当前值，取决于 sum + 当前值 是否大于 target ，如果大于就不再考虑，否则接着考虑。

Code：

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
57
58
59
60
61
class Solution {
public:
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        // write your code here
        vector<vector<int> > rs;
        vector<int> combination;
        sort(candidates.begin(), candidates.end());

        helper(candidates, target, 0, 0, combination, rs);

        set<vector<int> > s(rs.begin(), rs.end());
        rs.assign(s.begin(), s.end());

        return rs;
    }

    bool helper(vector<int> &num, int target, int sum, int n, vector<int> combination, vector<vector<int> > &rs) {
        bool isCountSelf = false;
        vector<int> currCombination = combination;
        if (n == num.size()) {
            if (sum == target) {
                rs.push_back(combination);
                return true;
            }
            return false;
        }

        if (sum + num[n] < target || sum + num[n] == target) { //backtracking
            isCountSelf = true;
            currCombination.push_back(num[n]);
            if (sum + num[n] == target) {
                helper(num, target, sum + num[n], num.size(), currCombination, rs);
            }
            else {
                helper(num, target, sum + num[n], n, currCombination, rs);
            }
        }
        else {
            return false;
        }
        if (isCountSelf) currCombination.pop_back();
		
        helper(num, target, sum, n + 1, currCombination, rs);

        if (sum + num[n] < target || sum + num[n] == target) { //backtracking
            currCombination.push_back(num[n]);
            if (sum + num[n] == target) {
                helper(num, target, sum + num[n], num.size(), currCombination, rs);
            }
            else {
                helper(num, target, sum + num[n], n + 1, currCombination, rs);
            }
        }
        return false;
    }
};