【LeetCode】 39. Combination Sum

Description

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

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

Note:

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

給一個數字集合(不重複)和一個目標數字target，找到所有集合中的組合，裡面的總合等於target。

在集合中的數字可以被重複選取好幾次。

注意：

• 所有數字(包含target)都是正整數。
• 答案集合不應該包含重複的組合。

Example:

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]


Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Solution

• 用遞迴求所有組合可能，對於特定狀況進行剪枝加速。
• 情況分為三種：
  • 拿現在的數字，下一次再拿現在的數字。
  • 拿現在的數字，下一次拿下一個數字。
  • 不拿現在的數字，下一次拿下一個數字。
    • 狀況三和狀況一可能導致取到重複的數字，因此我使用一個boolean來判斷是否為重複選取的情況。
• 如果總合已經超過目標值，就直接剪枝，因為數字都是正整數。
  • 也因為這點，在遞迴之前得先排列，不然可能錯誤剪枝。
• 可以將一些重複的東西用指標或參考傳遞參數，否則速度會很慢(call by value須花費較多時間)。

Code

class Solution {
public:
    
    void FindCombination(vector<vector<int>> &ans,vector<int> &candidates, vector<int> combination,int index,int &target,int sum,bool isDuplicates)
    {
        if(index == candidates.size()) return;
        combination.push_back(candidates[index]);
        sum+=candidates[index];
        if(sum==target) ans.push_back(combination);
        else if(sum>target) return;
        else
        {
            FindCombination(ans,candidates,combination,index,target,sum,true);
            FindCombination(ans,candidates,combination,index + 1,target,sum,false);
            
            if(!isDuplicates)
            {
                sum-=candidates[index];
                combination.pop_back();
                FindCombination(ans,candidates,combination,index + 1,target,sum,false);
            }
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        sort( candidates.begin(), candidates.end() );
        FindCombination(ans,candidates,vector<int>(0,0),0,target,0,false);
        return ans;
    }
};

tags: LeetCode C++