Combination sum 系列问题

1. Combination Sum
   Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
   The same repeated number may be chosen from candidates unlimited number of times.
   DFS问题：有入栈、有出栈

public  List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (candidates == null) {
            return result;
        }

        List<Integer> combination = new ArrayList<>();
        Arrays.sort(candidates);
        helper(candidates, 0, target, combination, result);

        return result;
    }

     void helper(int[] candidates,
                 int index,
                 int target,
                 List<Integer> combination,
                 List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<Integer>(combination));
            return;
        }
        if(target <0) return;

        for (int i = index; i < candidates.length; i++) {
            combination.add(candidates[i]);
            helper(candidates, i, target - candidates[i], combination, result);
            combination.remove(combination.size() - 1);
        }
    }

2. Combination Sum II 组合之和之二
   题目：
   Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
   Each number in C may only be used once in the combination.
   解题：
   DFS思想： 按照小->大排序后，从前往后逐一作为开始元素，再接着往后DFS下去。返回时，记得出栈

public List<List<Integer>> combinationSum2(int[] candidates,
            int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return results;
        }

        Arrays.sort(candidates);
        List<Integer> combination = new ArrayList<Integer>();
        helper(candidates, 0, combination, target, results);

        return results;
    }

    private void helper(int[] candidates, 
                        int startIndex, // 开始的index
                        List<Integer> combination, // 改组遍历 目前的成果
                        int target, // 目标值
                        List<List<Integer>> results) {
        if (target == 0) {
            results.add(new ArrayList<Integer>(combination));
            return;
        }
        if(target <0) return;

        for (int i = startIndex; i < candidates.length; i++) {
            if (i != startIndex && candidates[i] == candidates[i - 1]) { // 保证一个数字只用一次
                continue;
            }
  
            combination.add(candidates[i]);
            helper(candidates, i + 1, combination, target - candidates[i], results);
            combination.remove(combination.size() - 1);
        }
    }

3. Combination Sum III
   Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

All numbers will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
DFS问题

public int[] nums = {1,2,3,4,5,6,7,8,9};
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> combineList = new ArrayList<Integer>();
        dp(n, 0, combineList, k);
        return result;
    }
    
    public void dp(int restSum,
            int startIndex, 
            List<Integer> combineList,
            int restN){

        if(restSum ==0 && restN == 0){ 
            result.add(new ArrayList<Integer>(combineList)); // 注意这里一定要这种添加方式，不然就是引用了。dp返回后，combineList的remove操作会影响result
            return;
        }
        if(restSum <0 ){ // 如果剩余的sum不够了，返回
            return;
        }
        if(restN<=0){ // 如果剩余的位置不够了，返回
            return;
        }
        
        for(int i=startIndex; i<nums.length;i++){
            if(nums[i] > restSum)
                break;
            
            combineList.add(nums[i]);
            dp(restSum-nums[i], i+1, combineList, restN-1);
            combineList.remove(combineList.size()-1);
        }
        
    }

4. Combination Sum IV
   Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.
每个数字可以利用多次，属于动态规划问题

public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        
        // 外层遍历：sum总和
        for(int sum=1;sum<=target;sum++){
            // 内层遍历：各个num数字
            for(int num: nums){
                if(num<=sum){
                    dp[sum] += dp[sum-num];
                }
            }   
        }
        return dp[target];
    }