135.数字组合

描述

给出一组候选数字(C)和目标数字(T),找到C中所有的组合，使找出的数字和为T。C中的数字可以无限制重复被选取。

注意事项

所有的数字(包括目标数字)均为正整数。
元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
解集不能包含重复的组合。

样例

例如,给出候选数组[2,3,6,7]和目标数字7，所求的解为：

    [7]，
    [2,2,3]

与subsets题目区别：

1.本题每个数可以选多次，搜索时从index开始，subsets每个题只能选一次，选过的数不能再选，所以每次递归都index + 1
2.subsets无重复元素，本题有重复元素，本题需要先去重
3.本题的组合需要满足target条件，需加target参数来限制，subsets无需满足

PS

subsets的每个中间状态都是要的答案，而本题并不是每个中间状态都有用，所以不需要保留每个中间状态,bfs算法做本题需要同时保留大量中间态，dfs则不需要

代码

public class Solution {
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return results;
        }
       
        int[] nums = removeDuplicates(candidates);
        List<Integer> combination = new ArrayList<>();
        dfs(nums, 0, 0, results, combination, target);
        return results;
    }
    
    // 递归的定义，寻找以combination开头的所有组合，把它们都放到result中去
    // 注意dfs不需要任何返回值，用void
    private void dfs(int[] nums,
                     int startIndex,
                     int sum,
                     List<List<Integer>> results,
                     List<Integer> combination,
                     int target) {
        // 递归的出口
        if (sum == target) {
            // deep copy
            List<Integer> copy = new ArrayList<Integer>(combination);
            results.add(copy);
            return;
        }
        
        // 递归的拆解
        // [3] -> [3, 3] [3, 6] [3, 7]
        for (int i = startIndex; i < nums.length; i++) {
            // 结束这一层dfs，后面数都比当前数大，和都大于target
            if (sum + nums[i] > target) {
                break;      
            }
            combination.add(nums[i]);
            // 选过的数字可以再选，所以此处的startIndex是i
            dfs(nums, i, sum + nums[i], results, combination, target);
            // 回溯，结束本层dfs后，移除combination中的nums[i]，恢复成上一层dfs的combination
            combination.remove(combination.size() - 1);
        }
    }
    
    
    
    // 去掉数组中重复数的影响，每个数可以重复调用，没必要在数组里存在重复数
    // 用两根指针去重
    // i为遍历数组的指针，index指向数组中最后一个不重复数，把不重复的数全部移到数组最前面
    private 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];
            }
        }
        // 数组是从0开始的，index要加1
        int[] nums = new int[index + 1];
        for (int i = 0; i <= index; i++) {
            nums[i] = candidates[i];
        }
        return nums;
    }
}