My solution without using set


  • 6
    P

    My idea is skip same number during recursion. Like Permutations II. Firstly sort num, then search from back for numbers sum to target.

    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int>> res;
        sort(num.begin(), num.end());
        vector<int> cur;
        find(num, target, num.size() - 1, res, cur);
        return res;
    }
    
    void find(vector<int> &num, int target, int end, vector<vector<int>>& res, vector<int>& cur)
    {
        if (target == 0)
        {
            res.push_back(cur);
            return;
        }
        if (end < 0 || num[end] * (end + 1) < target) 
            return;
        
        if (num[end] <= target)
        {
            cur.insert(cur.begin(), num[end]);
            find(num, target - num[end], end - 1, res, cur);
            cur.erase(cur.begin());
        }
        //find combinations ends at the first number different from num[end]
        int temp = num[end];
        while (end >= 0 && num[end] == temp) end--;
        find(num, target, end, res, cur);
    }

  • 12
    W

    Nice code. But insertion at the beginning of a vector is expensive. If u build the result from the beginning like my code does, u can reduce the time to 24ms.

    void comb(vector<int>& num, int st, int target, vector<int>& psol, vector<vector<int> >& result){
          //processing num[st...] ,  psol: partial solution
            if(target==0){
                result.push_back(psol);
            }else{
                if( st==num.size() ) return; //cannot make it return directly
                int newtarget = target - num[st];
                if(newtarget>=0){
                    psol.push_back(num[st]);
                    comb(num, st+1, newtarget, psol, result);
                    psol.pop_back();
                    int i=st+1;
                    while( i<num.size() && num[i]==num[i-1] ) { i++; } //skip dups
                    comb(num, i, target, psol, result); //skip all values == num[st]
                    
                }//else cannot make it stop immediately
            }
                    
        }
        vector<vector<int> > combinationSum2(vector<int> &num, int target) {//O(2^n) time + O(n) space
            vector<vector<int> > result;
            vector<int> psol;
            std::sort(num.begin(), num.end());
            comb(num, 0, target, psol, result);
            return result;
        }

  • 5
    M

    Here's a Java version:

    public class Solution {
        public List<List<Integer>> combinationSum2(int[] num, int target) {
            List<List<Integer>> combos = new LinkedList<>();
            if (num == null || num.length == 0) return combos;
            Arrays.sort(num);
            combinationSum(num, target, new LinkedList<Integer>(), 0, combos);
            return combos;
        }
        
        private void combinationSum(int[] num, int target, List<Integer> list, int start, List<List<Integer>> combos) {
            if (target == 0) {
                combos.add(list);
            } else {
                int prev = 0;
                for (int i = start; i < num.length; i++) {
                    if (num[i] == prev) continue;
                    int nextTarget = target - num[i];
                    if (nextTarget >= 0) {
                        List<Integer> copy = new LinkedList<>(list);
                        copy.add(num[i]);
                        combinationSum(num, nextTarget, copy, i + 1, combos);
                    } else {
                        break;
                    }
                    prev = num[i];
                }
            }
        }
    }

  • 0
    L

    num[end] * (end + 1) < target

    the statement above means that since num[end] is the largest number, end+1 is the number of elements. If the sum of all these elements are still less than the target, it is meaningless to continue.


  • 0
    S

    Thanks for sharing your code. My code was almost the same as yours, except
    that I had used if (i>0 && num[i] == num[i-1]) continue;
    instead of the line in your code
    if (num[i] == prev) continue;

    My original code failed for test case [1,1] and target 2. Figured out the reason after reading your code. Thanks!


  • 0
    T

    my version, similar, I think I ,managed to remove some of the code in the recursive find , above the comment line, so the result looks cleaner

    public class Solution {
        List<Integer> partialSolution ;
        List<List<Integer>> result = new  ArrayList<List<Integer>>();
        public List<List<Integer>> combinationSum2(int[] num, int target) {
            partialSolution = new ArrayList<Integer>();
            Arrays.sort(num);
            
            recursive(num,0, target);
            
            return new ArrayList<List<Integer>>(result);
        }
        
        private void recursive(int[] candidates,int low, int target) {
            if ( target == 0) {
                List<Integer> elem = new ArrayList<Integer>(partialSolution);
                result.add(elem);
                return;
            } else if ( target < 0) {
                return;
            }
            
            for(int i=low;i<candidates.length;i++) {
                if (i > low && candidates[i] == candidates[i-1]) continue;
                partialSolution.add(candidates[i]);
                recursive(candidates,  i+1, target - candidates[i]);
                partialSolution.remove(partialSolution.size()-1);
            }
            
            
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.