LintCode 题解丨Uber面试题：数字组合

给定一个候选数字的集合 candidates 和一个目标值 target. 找到 candidates 中所有的和为 target 的组合.

在同一个组合中, candidates 中的某个数字不限次数地出现.

所有数值 (包括 target ) 都是正整数.
返回的每一个组合内的数字必须是非降序的.
返回的所有组合之间可以是任意顺序.
解集不能包含重复的组合.
在线评测地址：LintCode 领扣
​
样例 1:

输入: candidates = [2, 3, 6, 7], target = 7
输出: [[7], [2, 2, 3]]
样例 2:

输入: candidates = [1], target = 3
输出: [[1, 1, 1]]
算法：DFS

解题思路

本题需要在给定一个候选数字的集合 candidates 中. 找到所有的和为目标值 target 的组合。
对于这种需要求解所有结果的问题，我们为了避免结果有遗漏或者重复，一般可以考虑使用搜索算法。而本题需要满足组合中选取的元素之和为一个目标值，这个可以作为深度优先搜索的边界判断条件，故本题可以使用深度优先搜索（DFS）算法。
算法流程

由于题目候选数字的集合candidates可能包含重复数字，且返回的结果要求组合内数字非降序，因此首先需对candidates进行升序排序并去重，得到新的数字集合candidatesNew；
对新的数字集合进行深度优先搜索，传入的参数包括：数字集合candidatesNew、当前的位置index、当前存入的组合current、距离目标值的差remainTarget、保存答案的列表result；
当remainTarget=0即达到边界，将current添加到result，回溯；
循环遍历index位置到数字集合的末尾，分别递归调用dfs；
递归步进为：remainTarget - candidatesNew[i]；
剪枝：当发现当前的数字加入已超过remainTarget可进行剪枝。
复杂度分析

时间复杂度：O(n^target/min), （拷贝过程视作O(1))，n为集合中数字个数，min为集合中最小的数字
每个位置可以取集合中的任意数字，最多有target/min个数字。
空间复杂度：O(n^target /min)，n为集合中数字个数，min为集合中最 小的数字
对于用来保存答案的列表，最多有n^target/min种组合
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.length == 0) {
        return results;
    }
    // 排序和去重
    int[] candidatesNew = removeDuplicates(candidates);
    // dfs
    dfs(candidatesNew, 0, new ArrayList<Integer>(), target, results);
    return results;
}

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];
        }
    }
    int[] candidatesNew = new int[index + 1];
    for (int i = 0; i < index + 1; i++) {
        candidatesNew[i] = candidates[i];
    }
    return candidatesNew;
}

private void dfs(int[] candidatesNew, int index, List<Integer> current, int remainTarget, List<List<Integer>> results) {
    // 到达边界
    if (remainTarget == 0) {
        results.add(new ArrayList<Integer>(current));
        return;
    }
    // 递归的拆解：挑一个数放入current
    for (int i = index; i < candidatesNew.length; i++) {
        // 剪枝
        if (remainTarget < candidatesNew[i]) {
            break;
        }
        current.add(candidatesNew[i]);
        dfs(candidatesNew, i, current, remainTarget - candidatesNew[i], results);
        current.remove(current.size() - 1);
    }
}

}
更多题解参考：
九章算法 - 帮助更多中国人找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧
​