Java solution using dfs, easy understand


  • 68
    L
     public List<List<Integer>> combinationSum2(int[] cand, int target) {
        Arrays.sort(cand);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        dfs_com(cand, 0, target, path, res);
        return res;
    }
    void dfs_com(int[] cand, int cur, int target, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList(path));
            return ;
        }
        if (target < 0) return;
        for (int i = cur; i < cand.length; i++){
            if (i > cur && cand[i] == cand[i-1]) continue;
            path.add(path.size(), cand[i]);
            dfs_com(cand, i+1, target - cand[i], path, res);
            path.remove(path.size()-1);
        }
    }

  • 2
    S

    Nice! Elegant! Nice and elegant!


  • 13
    Q

    what's the meaning of if (i > cur && cand[i] == cand[i-1]) continue;?, thanks a lot


  • 0
    M
    This post is deleted!

  • 0
    S

    To skip the duplicate entry.


  • 0
    Q

    ok, thanks ........


  • 0
    P

    path.add(cand[i]) is enough.


  • 0
    E

    fantastic solution


  • -1
    T

    I coded the exact same solution. :D


  • 0
    N

    What is the time complexity of this?


  • 0
    O

    you should not have this line since duplicate numbers can be used. Take the exercise example: 8 = 1 + 1 + 6.


  • 0
    F

    same question, in case[1,1]2, the algorithm works, it is because i > cur ?


  • 0

    time complexity is O(2^n)


  • 0
    S

    when dfs_com first 1, (1,1,6) has been added into the result list.
    indeed, all combination that begin with 1 has been handle when dfs_com first 1, so later 1 should be skipped.


  • 7
    C

    For those who don't understand how to avoid duplicate by:
    if "(i > cur && cand[i] == cand[i-1]) continue;

    when we should skip a number? not just it's the same as previous number, but also when it's previous number haven't been added!

    i > cur means cand[i - 1] is not added to the path (you should know why if you understand the algorithm), so if cand[i] == cand[i-1], then we shouldn't add cand[i].

    This tricky is very smart.


  • 1
    C

    For those who don't understand how to avoid duplicate by: if "(i > cur && cand[i] == cand[i-1]) continue;

    when we should skip a number? not just it's the same as previous number, but also when its previous number haven't been added!

    i > cur means cand[i - 1] is pop from path (you should know why if you understand the algorithm), so if cand[i] == cand[i-1], then we shouldn't add cand[i].

    This tricky is very smart.


  • 4
    A

    I think the most important reason when we should skip a number which is the same as previous is that the previous number has been selected and added to the solution set, not hasn't been added.


  • 1
    X

    I can't understand path.remove(path.size()-1),what does it mean?


  • 1
    C

    [1,1,1]
    Let's think when should we skip the third 1, only when we add the first 1 but has not added the second 1, which implies that we only need to use one "1", rather than two "1", so skip the third "1".

    If we need to use two or three "1", the second "1" is used, then the third "1" won't be skipped .

    As for your concern, if the first and second "1" are selected, do we skip the third ? of course not, because we may use three "1".


  • 0
    C

    we have two choice, select the number or not.

    we push it into vector means we select it, pop it out means we don't select....


Log in to reply
 

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