Recursive java solution without loop


  • 0
    M

    The trick is to skip the number if it is the same as the last one on the current sum (see last if). In other words, if I use a repeated number A, I force all the following A's to be used. If I skip the number, the next A is still a candidate for the sum.

    public class Solution {
        public List<List<Integer>> combinationSum2(int[] num, int target) {
            List<List<Integer>> r = new ArrayList<>();
            Arrays.sort(num);
            combinationSum2(num, 0, target, new ArrayDeque<>(), r);
            return r;
        }
        private void combinationSum2(int[] num, int i, int target, Deque<Integer> cur, List<List<Integer>> r) {
            if (target == 0) {
                if (i >= num.length || cur.isEmpty() || cur.peekLast() != num[i]) {
                    r.add(new ArrayList<>(cur));
                }
                return;
            }
            if (target < 0 || i >= num.length) {
                return;
            }
      
            cur.addLast(num[i]);
            combinationSum2(num, i+1, target-num[i], cur, r);
            cur.removeLast();
            if (cur.isEmpty() || cur.peekLast() != num[i]) {
                combinationSum2(num, i+1, target, cur, r);
            }
        }
    }

  • 0
    I

    Why do you need this condition : cur.isEmpty() || cur.peekLast() != num[i]
    In the if target == 0 part? and also, why does the index need to be >= the length of candidates, as long as the target is reached it doesn't matter right?


Log in to reply
 

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