Combination Sum II

LeetCode #40

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.

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

Example:

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

Idea:

典型的backtraking，遇到goal，就算一个解，然后继续explore。先mark现在的点，explore完了之后backtrak现在的点。

这个因为不能重复，比如[1, 7], [1, 7]，但是可以[1,1,6]，所以同一个level的相同数不可以用两次，不同level的可以。

Code:

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { 
        vector<vector<int>> result;
        vector<int> curr_sequence;

        // 也可以是从小到大排列，从大到小主要因为类似找钱，先找大的
        sort(candidates.begin(), candidates.end(), [](int a, int b){return a>b;});

        DFS(candidates, 0, target, curr_sequence, result);

        return result;     
    }

    void DFS(const vector<int>& nums, int loc, int remain, vector<int>& curr_sequence, vector<vector<int>>& result){
        if(remain==0){
            result.push_back(curr_sequence);
            return;
        }
        int previous=-1;
        for(int i=loc; i<nums.size(); ++i){
            if(remain>=nums[i]){
                // 在同一个level，避免使用相同的数两次
                if(previous==nums[i]) 
                    continue;

                previous=nums[i];
                curr_sequence.push_back(nums[i]);
                DFS(nums, i+1, remain-nums[i], curr_sequence, result);
                curr_sequence.pop_back();
            }
        }

    }
};