A solution avoid using set


  • 29
    D

    Sort the candidates and we choose from small to large recursively, every time we add a candidate to our possible sub result, we subtract the target to a new smaller one.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        Arrays.sort(candidates); // sort the candidates
        // collect possible candidates from small to large to eliminate duplicates,
        recurse(new ArrayList<Integer>(), target, candidates, 0, ret);
        return ret;
    }
    
    // the index here means we are allowed to choose candidates from that index
    private void recurse(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> ret) {
        if (target == 0) {
            ret.add(list);
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            int newTarget = target - candidates[i];
            if (newTarget >= 0) {
                List<Integer> copy = new ArrayList<Integer>(list);
                copy.add(candidates[i]);
                recurse(copy, newTarget, candidates, i, ret);
            } else {
                break;
            }
        }
    }

  • 8
    Z

    Slightly modified your solution, this will make the method run a little faster.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        Arrays.sort(candidates); // sort the candidates
        // collect possible candidates from small to large to eliminate duplicates,
        recurse(new ArrayList<Integer>(), target, candidates, 0, ret);
        return ret;
    }
    
    // the index here means we are allowed to choose candidates from that index
    private void recurse(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> ret) {
        if (target == 0) {
            ret.add(list);
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            int newTarget = target - candidates[i];
            if (newTarget >= 0) {
                List<Integer> copy = new ArrayList<Integer>(list);
                copy.add(candidates[i]);
                recurse(copy, newTarget, candidates, i, ret);
            }else{
    break;
    }
        }

  • 1
    D

    That's a good break


  • 2
    S

    I don't get why you guys need the for loop, totally unnecessary.

    class Solution {
    public:
        vector<vector<int> > result;
        vector<int> output;
        
        vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
            sort(candidates.rbegin(), candidates.rend());
            search(candidates.begin(), candidates.end(), target);
            return result;
        }
        
        void search(vector<int>::iterator begin, vector<int>::iterator end, int target) {
            if (target == 0) {
                result.push_back(output);
                sort(result.back().begin(), result.back().end());
                return;
            }
            
            if (begin == end)
                return;
                
            if (*begin <= target) {
                output.push_back(*begin);
                search(begin, end, target-*begin);
                output.pop_back();
            }
            
            search(begin+1, end, target);
        }
    };

  • 0
    B

    what is the time and space complexity of this solution? Seems like it would be:

    Time: O(n*m), where n is size of candidate set, and m == target. Consider target = 1 million, and set = (1,2,3). On the first iteration, we would recurse a million times to form the set (1,1,1,1....). 2 would be 500,000 recursions.

    Space: O(m) due to stack frames


  • 0
    S
    This post is deleted!

  • 0
    S

    Regarding your code, what if you meet candidates = [1,1], target = 1. It's gonna output [[1],[1]]. And also, the time complexity is O(n!) scale

    Yeah, you're correct! Even though this case happens, it is easily checked using a HashSet.


  • 0
    D

    For this problem, I think the assumption is there's no duplicate in candidates.


  • 0
    Z

    Hi what's your former code without using the "break".

    I came out with a similar way with yours. But I didn't realize the else {} should use break

    Thanks


  • 0
    D

    Just delete the else clause is my former code.


  • 0
    A

    the code above cannot generate unique answers when the candidates contain same numbers. ex: [2, 2, 3, 6, 7], target = 7. it will generate [2, 2, 3] three times.


  • 1
    A

    the code above cannot generate unique answers when the candidates contain same numbers. ex: [2, 2, 3, 6, 7], target = 7. it will generate [2, 2, 3] three times.

    my code here will skip the number that are same as the next number.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(candidates.length <= 0)
    return res;
    Arrays.sort(candidates);
    ArrayList<Integer> line = new ArrayList<Integer>();
    finder(res, line, target, candidates, 0);
    return res;
    }
    public void finder(List<List<Integer>> res, ArrayList<Integer> line, int target, int[] candidates, int i)
    {
    if(target == 0)
    {
    res.add(line);
    return;
    }
    if(i >= candidates.length)
    return;
    if(target < 0)
    return;
    for(int j = i; j < candidates.length; j++)
    {
    //skip the same integers
    while(j+1 < candidates.length && candidates[j+1] == candidates[j])
    {
    j++;
    }
    if(target-candidates[j] >= 0)
    {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    tmp.addAll(line);
    tmp.add(candidates[j]);
    finder(res, tmp, target-candidates[j],candidates,j);
    }
    }
    }


  • 0
    D

    Please format your code so we can continue the discussion


  • 0
    P

    Nice, but why reverse the candidates then reverse the output back again?


  • 0
    L

    I think newTarget should >= candidates[i], not 0. In that case, we can reduce some cases.
    What's more, I think there may be some memory leaks. i.e. [1,2,3,4],target 6, when you test [2, 3 ....], you will copy array [2, 3], but you will not free it .


  • 0
    T

    To keep the results in non-descending order


  • 0
    Y

    i think the question implies that there will be no duplicates in the candidates, since it says the candidates is a set.


  • 0
    D

    Yes, that makes a lot of sense


  • 0
    S

    Would this not generate multiple copies of [1,1] for inputs like [1,1,1,1] and target = 2 ?


  • 0
    Z

    You are right. The assumption of this answer is candidates[] has all unique numbers.

    To avoid duplicate in your example, you can add below line in the beginning of the loop :) if(i>index&&candidates[i]==candidates[i-1]) continue;


Log in to reply
 

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