「力扣」第 39 题:组合总和


「力扣」第 39 题:组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入: candidates = [2, 3, 6,7], target = 7,
所求解集为:
[
  [7],
  [2, 2, 3]
]

示例 2:

输入: candidates = [2, 3, 5], target = 8,
所求解集为:
[
  [2, 2, 2, 2],
  [2, 3, 3],
  [3, 5]
]

思路:

  • 先画树形图
  • 回溯算法 = 树形问题上的深度优先遍历;
  • 理解如何去重:每次搜索的起点不能比上一次还早;
  • 排序是为了剪枝。

Java 代码:

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>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = candidates.length;

        // 排序是为了提前终止搜索
        Arrays.sort(candidates);

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

    /**
     * @param candidates 数组输入
     * @param len        输入数组的长度,冗余变量
     * @param residue    剩余数值
     * @param begin      本轮搜索的起点下标
     * @param path       从根结点到任意结点的路径
     * @param res        结果集变量
     */
    private void dfs(int[] candidates,
                     int len,
                     int residue,
                     int begin,
                     Deque<Integer> path,
                     List<List<Integer>> res) {
        if (residue == 0) {
            // 由于 path 全局只使用一份,到叶子结点的时候需要做一个拷贝
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < len; i++) {

            // 在数组有序的前提下,剪枝
            if (residue - candidates[i] < 0) {
                break;
            }

            path.addLast(candidates[i]);
            dfs(candidates, len, residue - candidates[i], i, path, res);
            path.removeLast();
        }
    }
}

文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 40 题:组合总和 II 「力扣」第 40 题:组合总和 II
「力扣」第 40 题:组合总和 II 链接 题解链接 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合
下一篇 
「力扣」第 47 题:全排列 II 「力扣」第 47 题:全排列 II
「力扣」第 47 题:全排列 II 链接 题解链接(含视频讲解) 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1, 1, 2] 输出: [ [1, 1, 2], [1, 2, 1], [2, 1
  目录