关注Java领域相关技术 记录有趣的事情

LeetCode-39. 组合总和

US-B.Ralph
US-B.Ralph
2020-09-092020-09-18

问题地址

LeetCode每日一题/2020-09-09

LeetCode39. 组合总和


问题描述

规则

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

说明

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

示例

  • 示例一:
输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
  • 示例二:
输入:candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

提示

  • $1 <= candidates.length <= 30$
  • $1 <= candidates[i] <= 200$
  • candidate 中的每个元素都是独一无二的。
  • $1 <= target <= 500$

解析

解题思路

数据操作分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现


官方解法

方法一:搜索回溯

思路:

  • 对于这类寻找所有可行解的题,我们都可以尝试用「搜索回溯」的方法来解决。
  • 回到本题,我们定义递归函数 dfs(target, combine, idx) 表示当前在 candidates 数组的第 idx 位,还剩 target 要组合,已经组合的列表为 combine。递归的终止条件为 target = 0$ 进行剪枝,所以实际运行情况是远远小于这个上界的。
  1. 空间复杂度:O(target)。除答案数组外,空间复杂度取决于递归的栈深度,在最差情况下需要递归 O(\textit{target}) 层。

编码实现

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }
}

精彩评论

跳转地址1:回溯算法 + 剪枝(回溯经典例题详解)

思路

  • 根据示例 1:输入: candidates = [2, 3, 6, 7],target = 7。
    • 候选数组里有 2,如果找到了组合总和为 7 – 2 = 5 的所有组合,再在之前加上 2 ,就是 7 的所有组合;
    • 同理考虑 3,如果找到了组合总和为 7 – 3 = 4 的所有组合,再在之前加上 3 ,就是 7 的所有组合,依次这样找下去。
  • 基于以上的想法,可以画出如下的树形图。建议大家自己在纸上画出这棵树,这一类问题都需要先画出树形图,然后编码实现
  • 编码通过 深度优先遍历 实现,使用一个列表,在 深度优先遍历 变化的过程中,遍历所有可能的列表并判断当前列表是否符合题目的要求,成为「回溯算法」(个人理解,非形式化定义)。
  • 回溯算法的总结我写在了「力扣」第 46 题(全排列)的题解 《回溯算法入门级详解 + 经典例题列表(持续更新)》 中,如有需要请前往观看。

画出树形图

  • 2020 年 9 月 9 日补充:以下给出的是一种树形图的画法。对于组合来说,还可以根据一个数选和不选画树形图,请参考 官方题解 或者 @elegant-pike 的 评论。
  • 以输入:candidates = [2, 3, 6, 7], target = 7 为例:

说明

  • 以 target = 7 为 根结点 ,创建一个分支的时 做减法 ;
  • 每一个箭头表示:从父亲结点的数值减去边上的数值,得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值;
  • 减到 00 或者负数的时候停止,即:结点 00 和负数结点成为叶子结点;
  • 所有从根结点到结点 00 的路径(只能从上往下,没有回路)就是题目要找的一个结果。

  • 这棵树有 44 个叶子结点的值 00,对应的路径列表是 [[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]],而示例中给出的输出只有 [[7], [2, 2, 3]]。即:题目中要求每一个符合要求的解是 不计算顺序 的。下面我们分析为什么会产生重复。

针对具体例子分析重复路径产生的原因(难点)

  • 产生重复的原因是:在每一个结点,做减法,展开分支的时候,由于题目中说 每一个元素可以重复使用,我们考虑了 所有的 候选数,因此出现了重复的列表。
  • 一种简单的去重方案是借助哈希表的天然去重的功能,但实际操作一下,就会发现并没有那么容易。
  • 可不可以在搜索的时候就去重呢?答案是可以的。遇到这一类相同元素不计算顺序的问题,我们在搜索的时候就需要 按某种顺序搜索。具体的做法是:每一次搜索的时候设置 下一轮搜索的起点 begin,请看下图。
  • 即:从每一层的第 22 个结点开始,都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。

复杂度分析

  • 这个问题的复杂度分析是在我的能力之外的,这里给出我的思考。
  • 我的结论是:时间复杂度与 candidate 数组的值有关:
    • 如果 candidate 数组的值都很大,target 的值很小,那么树上的结点就比较少;
    • 如果 candidate 数组的值都很小,target 的值很大,那么树上的结点就比较多。
  • 所以时间复杂度与空间复杂度不确定。

补充

  • 参考代码 1 和参考代码 2 的 Python 部分,没有严格按照回溯算法来写,这里需要了解的知识点是:
    • Python3 的 [1, 2] + [3] 语法生成了新的列表,一层一层传到根结点以后,直接 res.append(path) 就可以了;
    • 基本类型变量在传参的时候,是复制,因此变量值的变化在参数里体现就行,所以 Python3 的代码看起来没有「回溯」这个步骤。

编码实现

参考代码一

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

public class Solution {

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

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

    /**
     * @param candidates 候选数组
     * @param begin      搜索起点
     * @param len        冗余变量,是 candidates 里的属性,可以不传
     * @param target     每减去一个元素,目标值变小
     * @param path       从根结点到叶子结点的路径,是一个栈
     * @param res        结果集列表
     */
    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 重点理解这里从 begin 开始搜索的语意
        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);

            // 注意:由于每一个元素可以重复使用,下一轮搜索的起点依然是 i,这里非常容易弄错
            dfs(candidates, i, len, target - candidates[i], path, res);

            // 状态重置
            path.removeLast();
        }
    }
}

参考代码二:增加控制台输出

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

public class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i <= n; i++) {
            path.addLast(i);
            System.out.println("递归之前 => " + path);
            dfs(n, k, i + 1, path, res);
            path.removeLast();
            System.out.println("递归之后 => " + path);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 5;
        int k = 3;
        List<List<Integer>> res = solution.combine(n, k);
        System.out.println(res);
    }
}

优化:剪枝提速

思路

  • 根据上面画树形图的经验,如果 target 减去一个数得到负数,那么减去一个更大的树依然是负数,同样搜索不到结果。基于这个想法,我们可以对输入数组进行排序,添加相关逻辑达到进一步剪枝的目的;
  • 排序是为了提高搜索速度,对于解决这个问题来说非必要。但是搜索问题一般复杂度较高,能剪枝就尽量剪枝。实际工作中如果遇到两种方案拿捏不准的情况,都试一下。

复杂度分析

  1. 时间复杂度:。
  2. 空间复杂度:。

编码实现

参考代码三:

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) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 排序是剪枝的前提
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // 由于进入更深层的时候,小于 0 的部分被剪枝,因此递归终止条件值只判断等于 0 的情况
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < len; i++) {
            // 重点理解这里剪枝,前提是候选数组已经有序,
            if (target - candidates[i] < 0) {
                break;
            }

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

总结

什么时候使用 used 数组,什么时候使用 begin 变量

  • 有些朋友可能会疑惑什么时候使用 used 数组,什么时候使用 begin 变量。这里为大家简单总结一下:
    • 排列问题,讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时),需要记录哪些数字已经使用过,此时用 used 数组;
    • 组合问题,不讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时),需要按照某种顺序搜索,此时使用 begin 变量。
  • 注意:具体问题应该具体分析, 理解算法的设计思想 是至关重要的,请不要死记硬背。

补充说明

  • 如果对于「回溯算法」的理解还很模糊的朋友,建议在「递归」之前和「递归」之后,把 path 变量的值打印出来看一下,以加深对于程序执行流程的理解。

  • 针对参考代码 1 添加打印输出:

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


public class Solution {

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

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

    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < len; i++) {
            path.addLast(candidates[i]);
            System.out.println("递归之前 => " + path + ",剩余 = " + (target - candidates[i]));

            dfs(candidates, i, len, target - candidates[i], path, res);

            path.removeLast();
            System.out.println("递归之后 => " + path);

        }
    }

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

  • 针对参考代码 2 添加打印输出:
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) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

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

    private void dfs(int[] candidates, int begin, int len, 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++) {
            if (target - candidates[i] < 0) {
                break;
            }

            path.addLast(candidates[i]);
            System.out.println("递归之前 => " + path + ",剩余 = " + (target - candidates[i]));

            dfs(candidates, i, len, target - candidates[i], path, res);
            path.removeLast();
            System.out.println("递归之后 => " + path);
        }
    }

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

跳转地址2:超强gif助你理解使用“动态规划”求解本题

前言

  • 看这题的题解,大家都是用回溯法解的。随着我把组合总和的IIIIIIV做完,尤其是到IV的时候,回溯算法就超时了,而IV恰好是用动态规划解决的,于是我就思考:能不能用动态规划求解本题。

思路

  • 对于目标值target,它一定是由比它小的数相加得到的。比如5=1+4=2+3,而4=3+1=2+2,3=2+1,2=1+1…, 也就是说,从1开始,我们依次求解每个数可以有几种形成的方式,则数值更高的数的组合方式建立在数值低的数的组合方式上得到,好吧我自己都没看懂我说的话,直接看图片吧。

准备工作

  • 初始化一个数组dict,键是1~target,值初始化为空列表。

分析组成方式

  • 得到:1只可以由[1]这1种方式组成。
  • 得到:2只可以由[1,1],[2]这2种方式组成。
  • 得到:3可以由[1,1,1],[1,2],[3]这3种方式组成。
  • 得到:4可以由[1,1,1,1],[1,1,2],[2,2],[3,1],[4]这5种方式组成。
  • 得到:5可以由[1,1,1,1,1],[1,1,1,2],[2,2,1],[3,1,1],[3,2],[4,1]这6种方式组成。

总结

  • 求解一个值,需要求解上一个值,进而需要求解上上个值…,这种方法就是动态规划。重复的值只需要进行一次,而后再使用到这个值时,只需要将他的结果拿来适当增加即可。

感谢

  • 受编程水平限制,博主最初只提供了Python3的代码,欢迎其他编程语言爱好者提供相应代码复现动态规划。
    • C++版本1算法由@lan-yun-2提供。
    • C++版本2算法由@pris_bupt提供。
    • Java算法由@liu-li-8提供。
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        dict = {}
        for i in range(1,target+1):
            dict[i]=[]

        for i in range(1,target+1):
            for j in candidates:
                if i==j:
                    dict[i].append([i])
                elif i>j:
                    for k in dict[i-j]:
                        x = k[:]
                        x.append(j)
                        x.sort() # 升序,便于后续去重
                        if x not in dict[i]:
                            dict[i].append(x)

        return dict[target]
// 由@lan-yun-2提供
map<int, set<vector<int> > > dpkv;
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        set<vector<int> > avectorset;
        // 初始化
        for(int i = 1; i <= target; i++){
            dpkv[i] = avectorset; // 都赋值成一个空的数组
        }
        // 开始递推

        for(int j = 1; j <= target; j++){
            for(vector<int>::iterator it = candidates.begin(); it != candidates.end(); it++){
                if(j == *it){
                    // 直接作为一个vector<int>加入
                    vector<int> v_only_one_num;
                    v_only_one_num.push_back(j);
                    dpkv[j].insert(v_only_one_num);
                } else if(j > *it){ // 用dp[j - *it] 作为结果
                    // 遍历dp[j - *it]
                    for(set<vector<int> >::iterator its = dpkv[j - *it].begin(); its != dpkv[j - *it].end(); its++){
                        vector<int> the_vector = (*its);
                        the_vector.push_back(*it);
                        sort(the_vector.begin(), the_vector.end());
                        dpkv[j].insert(the_vector);
                    }
                }
            }
        }
        // 将set加工成vector
        vector<vector<int>> target_v;
        for(set<vector<int> >::iterator its = dpkv[target].begin(); its != dpkv[target].end(); its++){
            target_v.push_back(*its);
        }

        return target_v;
    }
};
// 由@pris_bupt提供
 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    unordered_map<int, set<vector<int>>>dict;
    for (int i = 1; i <= target; i++)
        for (int it : candidates) 
        if (i == it) dict[i].insert(vector<int>{it});
        else if (i > it)
             for (auto ivec : dict[i - it]) {
            ivec.push_back(it);
            sort(ivec.begin(), ivec.end());
            if(dict[i].count(ivec)==0)
                    dict[i].insert(ivec);
            }
    vector<vector<int>>ans;
    for (auto it : dict[target]) ans.push_back(it);
    return ans;
}
// 由@liu-li-8提供
class Solution {
  public List<List<Integer>> combinationSum(int[] candidates, int target) {
      List<List<Integer>> result = new ArrayList<>();
      Map<Integer,Set<List<Integer>>> map = new HashMap<>();
      //对candidates数组进行排序
      Arrays.sort(candidates);
      int len = candidates.length;
      for(int i = 1;i <= target;i++){
          //初始化map
          map.put(i,new HashSet<>());
          //对candidates数组进行循环
          for(int j = 0;j < len&&candidates[j] <= target;j++){
              if(i == candidates[j]){
                  //相等即为相减为0的情况,直接加入set集合即可
                  List<Integer> temp = new ArrayList<>();
                  temp.add(i);
                  map.get(i).add(temp);
              }else if(i > candidates[j]){
                  //i-candidates[j]是map的key
                  int key = i-candidates[j];
                  //使用迭代器对对应key的set集合进行遍历
                  //如果candidates数组不包含这个key值,对应的set集合会为空,故这里不需要做单独判断
                  for(Iterator iterator = map.get(key).iterator();iterator.hasNext();){
                      List list = (List) iterator.next();
                      //set集合里面的每一个list都要加入candidates[j],然后放入到以i为key的集合中
                      List tempList = new ArrayList<>();
                      tempList.addAll(list);
                      tempList.add(candidates[j]);
                      //排序是为了通过set集合去重
                      Collections.sort(tempList);
                      map.get(i).add(tempList);
                  }
              }
          }
      }
      result.addAll(map.get(target));
      return result;
  }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

1 × 2 =