LeetCode第39题分析

原题

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1 2	输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1 2	输入: candidates = [2], target = 1 输出: []

提示：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都互不相同
1 <= target <= 500

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

基本不用想就知道要使用递归，同时通过进一步的思考会发现如果使用递归算法将会产生大量的冗余计算，首先进入我的想法的是带存储器的递归，通过hashMap来避免重复计算。重新仔细阅读题目，发现hashMap在这个环境中不能正常工作，因为往往针对一个target有多种解法并不是一对一的关系。

分析题目可以发现递归过程可以作为一棵树，而这棵树中重复的节点是由于在产生子节点的时候考虑了所有的侯选数，只要按顺序考虑候选数就可以在不重复的前提下保证计算到所有的情况，如图：

接下来就可以写出对应的代码

package algorithms;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class question39 {
    static class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            if (candidates.length == 0)
                return res;
            Deque<Integer> tempRes = new ArrayDeque<>();
            dfs(candidates, target, 0, tempRes, res);
            return res;
        }

        public void dfs(int[] candidates, int target, int start, Deque<Integer> tempRes, List<List<Integer>> res) {
            if (target < 0)
                return;
            if (target == 0) {
                res.add(new ArrayList<>(tempRes));
                return;
            }
            for (int i = start; i < candidates.length; i++) {
                tempRes.addLast(candidates[i]);
                dfs(candidates,target-candidates[i],i,tempRes,res);
                tempRes.removeLast();
            }
        }
    }
}

优化

有了上面的代码这道题其实已经解决，但是上面的代码尚有优化空间，若candidates能够有序排列就可以做到在前一项加和已经过大时中断枚举过程省去后续的计算步骤。

代码如下

package algorithms;

import java.util.*;

public class question39 {
    static class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            if (candidates.length == 0)
                return res;
            Deque<Integer> tempRes = new ArrayDeque<>();
            Arrays.sort(candidates); //首先需要对candidates进行排序
            dfs(candidates, target, 0, tempRes, res);
            return res;
        }

        public void dfs(int[] candidates, int target, int start, Deque<Integer> tempRes, List<List<Integer>> res) {
            if (target < 0)
                return;
            if (target == 0) {
                res.add(new ArrayList<>(tempRes));
                return;
            }
            if (target < candidates[start]) //如果首项已经过大则没有必要继续枚举
                return;
            for (int i = start; i < candidates.length; i++) {
                tempRes.addLast(candidates[i]);
                dfs(candidates,target-candidates[i],i,tempRes,res);
                tempRes.removeLast();
            }
        }
    }
}

变体

package algorithms;

import java.util.*;

public class question39 {
    static class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            HashMap<List<Integer>,Integer> allRes = new HashMap<>();
            if (candidates.length == 0)
                return res;
            Deque<Integer> tempRes = new ArrayDeque<>();
            Arrays.sort(candidates);
            dfs(candidates, target, 0, tempRes, allRes);
            res.addAll(allRes.keySet());
            return res;
        }

        public void dfs(int[] candidates, int target, int start, Deque<Integer> tempRes, HashMap<List<Integer>,Integer> allRes) {
            if (target < 0)
                return;
            if (target == 0) {
                List<Integer> temp = new ArrayList<>(tempRes);
                allRes.put(temp,allRes.getOrDefault(temp,0) + 1);
//                res.add(new ArrayList<>(tempRes));
                return;
            }
            if (candidates.length == start)
                return;
            if (target < candidates[start])
                return;
            for (int i = start; i < candidates.length; i++) {
                tempRes.addLast(candidates[i]);
                dfs(candidates, target - candidates[i], i + 1, tempRes, allRes);
                tempRes.removeLast();
            }
        }
    }
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class Solution {

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

        // 关键步骤
        Arrays.sort(candidates);

        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(candidates, len, 0, target, path, res);
        return res;
    }

    /**
     * @param candidates 候选数组
     * @param len        冗余变量
     * @param begin      从候选数组的 begin 位置开始搜索
     * @param target     表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
     * @param path       从根结点到叶子结点的路径
     * @param res
     */
    private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < len; i++) {
            // 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
            if (target - candidates[i] < 0) {
                break;
            }

            // 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }

            path.addLast(candidates[i]);
            // 调试语句 ①
            // System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));

            // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
            dfs(candidates, len, i + 1, target - candidates[i], path, res);

            path.removeLast();
            // 调试语句 ②
            // System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));
        }
    }

    public static void main(String[] args) {
        int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        Solution solution = new Solution();
        List<List<Integer>> res = solution.combinationSum2(candidates, target);
        System.out.println("输出 => " + res);
    }
}