九章算法 | Uber面试题：数字组合

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

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

1. 所有数值 (包括 target ) 都是正整数.
2. 返回的每一个组合内的数字必须是非降序的.
3. 返回的所有组合之间可以是任意顺序.
4. 解集不能包含重复的组合.

在线评测地址：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）算法。

算法流程

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

更多题解参考：九章算法