Combination Sum II

Description:

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

Each number in C may only be used once in the combination.

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 [10,1,6,7,2,1,5] and target 8, A solution set is:

[
    [1,7],
    [1,2,5],
    [2,6],
    [1,1,6]
]

分析：

   这道题的另一种简单的变形是：能否从中找出数字相加和等于某一目标值。此时，并不需要找出所有的组合，只要找到一种满足的就可以返回 true 。

   另一种变形是：找出所有可能的组合总数目，这种变形和本题差不多。

   对于这道题，对于每一个数字有两种可能：要么加，要么不加。所以是一种二叉树的遍历/枚举。使用DFS 遍历所有可能的结果，当所有的数字都遍历了之后再判断相加和是否等于目标值，如果等于就进行相关操作，否则就直接返回 false。

   不过，如果直接使用DFS 时间复杂度过大，所以需要进行 剪枝 ，即使用 Backtarcking 。

思路：

  1. 当所有的数字都遍历了之后再判断相加和是否等于目标值，如果等于就进行相关操作，否则就直接返回 false。
  2. 不加上当前值，接着进行搜索。
  3. 当加上当前值不大于目标值时，加上当前值并进行搜索。这时有一种情况是：当加上当前值时如果正好等于目标值，就直接设置当前搜索深度为 A.size()。因为A中的数字都是正数，无论后面加不加都不再需要进行搜索，所以下一步直接返回。

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

#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class Solution {
public:
    /**
    * @param num: Given the candidate numbers
    * @param target: Given the target number
    * @return: All the combinations that sum to target
    */
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        // write your code here
        vector<vector<int> > rs;
        vector<int> combination;
        sort(num.begin(), num.end());

        helper(num, 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) {
        vector<int> currCombination = combination;
        if (n == num.size()) {
            if (sum == target) {
                rs.push_back(currCombination);
                return true;
            }
            return false;
        }

        helper(num, target, sum, n + 1, currCombination, rs);

        //if replace the next if clause with next 2 clause, it will be recursion/depth first search, time complexity = O(2^n), Time Limit Exceeded
        //currCombination.push_back(num[n]);
        //helper(num, target, sum + num[n], 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);
            }
        }
    }
};