Combination Sum

LeetCode #39

Description:

Given a set of candidate numbers (C) (without duplicates) 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.

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

Example:

For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 
[
  [7],
  [2, 2, 3]
]

Idea:

典型的backtraking，遇到goal，就算一个解，然后继续explore。先mark现在的点，explore完了之后backtrak现在的点。 跟Coin Change II有些类似。

Code:

class Solution {
public:
    vector<vector<int>> combinationSum(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;
        }

        for(int i=loc; i<nums.size(); ++i){
            if(remain>=nums[i]){
                curr_sequence.push_back(nums[i]);
                DFS(nums, i, remain-nums[i], curr_sequence, result);
                curr_sequence.pop_back();
            }
        }
    }
};