LeetCode:Combination Sum

Combination Sum

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.

Note:

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

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

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(candidates);
        ArrayList<ArrayList<Integer>> prev = new ArrayList<ArrayList<Integer>>();
        prev.add(new ArrayList<Integer>());
        return combinationSum(candidates,target,0,prev);
    }
    
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target, int i, ArrayList<ArrayList<Integer>> prev){
        ArrayList<ArrayList<Integer>> res = new  ArrayList<ArrayList<Integer>>();
        if(target==0){
            for(ArrayList<Integer> temp:prev){
                ArrayList<Integer> temp1 = new ArrayList<Integer>(temp);   
                res.add(temp1);
            }    
            return res;
        }    
        for(int j=i;j<candidates.length;j++){
            if(candidates[j]>target)
                break;
            for(ArrayList<Integer> temp:prev)
                temp.add(candidates[j]);    
            ArrayList<ArrayList<Integer>> next = combinationSum(candidates,target-candidates[j],j,prev);
            if(next.size()>0)
                res.addAll(next);
            for(ArrayList<Integer> temp:prev)
                temp.remove(temp.size()-1);
            }
        return res;
    }
}

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> output;
        vector<vector<int>> buffer = vector<vector<int>> (1, vector<int>());
        combinationSum(candidates, output, target, buffer, 0);
        return output;
    }
    
    void combinationSum(const vector<int> &candidates, vector<vector<int>> &output,
        int target, vector<vector<int>> &buffer, int index) {
        if (target == 0) {
            for (auto temp : buffer) {
                output.push_back(temp);
            }
        } else {
            for (int i = index; i < candidates.size(); ++i) {
                if ((i == index || candidates[i] != candidates[i-1]) && candidates[i] <=  target) {
                    for (int j = 0; j < buffer.size(); ++j) {
                        buffer[j].push_back(candidates[i]);
                    }    
                    combinationSum(candidates, output, target - candidates[i], buffer, i); 
                    for (int j = 0; j < buffer.size(); ++j) {
                        buffer[j].pop_back();
                    }   
                }
            }
        }
    }
};