Combination sum

這一題考驗的是會不會寫遞迴

寫遞迴三要件：定義、出口、拆解

看code吧：

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    // write your code here
    List<List<Integer>> results = new ArrayList<>();
    if (candidates == null || candidates.length == 0) {
        return results;
    }

    int[] nums = removeDuplicates(candidates);
    helper(nums, 0, target, new ArrayList<Integer>(), results);
    return results;
}

public int[] removeDuplicates(int[] candidates) {
    Arrays.sort(candidates);

    int index = 0;
    for (int i = 0; i < candidates.length; i++) {
        if (candidates[i] != candidates[index]) {
            candidates[++index] = candidates[i];
        }
    }
    int[] nums = new int[index + 1];    //because index is zero-based, so add 1
    for (int i = 0; i < index + 1; i++) {
        nums[i] = candidates[i];
    }
    return nums;
}

//recursion definition:
//every time pick a num from startIndex and see if target is matched
public void helper(int[] nums,
                   int startIndex,
                   int target,
                   List<Integer> combination,
                   List<List<Integer>> results) {
    //end condition
    if (target == 0) {
        results.add(new ArrayList<Integer>(combination));
        return;
    }

    for (int i = startIndex; i < nums.length; i++) {
        if (nums[i] > target) {
            break;  //over target
        }

        combination.add(nums[i]);
        helper(nums, i, target - nums[i], combination, results);
        combination.remove(combination.size() - 1);
    }
}

Follow up:

有重複的元素，那麼跟 subset II 一樣，先排序後如果前面一個跟我一樣我又不是開始的話，那麼不挑

public List<List<Integer>> combinationSum2(int[] num, int target) {
    // write your code here
    List<List<Integer>> results = new ArrayList<>();
    if (num == null || num.length == 0 || target < 0) {
        return results;
    }

    Arrays.sort(num);
    helper(num, 0, target, new ArrayList<Integer>(), results);
    return results;
}


public void helper(int[] nums,
                   int startIndex,
                   int remain,
                   List<Integer> combination,
                   List<List<Integer>> results) {
    if (remain == 0) {
        results.add(new ArrayList<Integer>(combination));
        return;
    }

    for (int i = startIndex; i < nums.length; i++) {

        if (nums[i] > remain) {
            break;
        }

        // i != startIndex represents it's not the start of the recursion
        if ( i - 1 >= 0 && nums[i] == nums[i - 1] && i != startIndex) {
            continue;
        }

        combination.add(nums[i]);
        helper(nums, i+1, remain - nums[i], combination, results);
        combination.remove(combination.size() - 1);
    }
}