0%

[0039] 组合总和

发表于 更新于 分类于 ， 本文字数： 2.1k 阅读时长 ≈ 2 分钟
...

[0039] 组合总和

题目描述

给定一个无重复元素的数组 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]
]

Related Topics
  • 数组
  • 回溯算法

    • 题目解析

    • 完全01背包问题

    不确定性

    • 整数的范围
    • 数字的范围
    • 数字是否会重复
    • candidates数组大小
    • 以上题目中虽然都有，审题要清楚不能想当然

    方法一：逐个尝试法

    分析

    • 对于每个数字采取选择0，1，2，。。。n的做法
    • 尝试过程中注意剪枝

    思路

    • 利用完全01背包

    • 伪代码如下：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      void dfs(dep, candidates, select, target)
      {
        if(target<0) return; // 由于被选数都是正数，无答案
        if(target==0) {// 答案满足
          res.add(select);
          return;
        }
        if(dep >= candidates.size()) return;// 所有的数字都用完了

        // 选择当前数字
        select.push(candidates[dep]);
        dfs(dep, candidates, select, target-candidates[dep]); // 由于当前这个数还有可能被选择，所以dep 还停留在当前。
        select.pop();

        // 不选择当前数
        dfs(dep+1, candidates, select, target);
      }

    注意

    • 要考虑整数加减法有可能溢出，根据题目给出的条件，应该不会有这种情况

    知识点

    • 01背包
    • 暴力
    • dfs

    复杂度

    • 时间复杂度O(NV), N是数组长度，V是target大小
    • 空间复杂度O(V), 代表递归深度

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    typedef long long lld;

    class Solution {
        vector<vector<int> > res;
        void dfs(int dep, vector<int> &candidates, vector<int> &select, lld target)
        {
            if(target<0) return; // 由于被选数都是正数，无答案
            if(target==0) {// 答案满足
                res.push_back(select);
                return;
            }
            if(dep >= candidates.size()) return;// 所有的数字都用完了

            // 不选择当前数
            dfs(dep+1, candidates, select, target);

            // 选择当前数字
            select.push_back(candidates[dep]);
            dfs(dep, candidates, select, target-candidates[dep]); // 由于当前这个数还有可能被选择，所以dep 还停留在当前。
            select.pop_back();
        }
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            res.clear();
            sort(candidates.begin(), candidates.end());
            vector<int> select;
            dfs(0, candidates, select, target);
            return res;
        }
    };

    相关题目

    相关文章