leetcode 40. 组合总和 II

题目

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意:解集不能包含重复的组合。

原题链接:https://leetcode.cn/problems/combination-sum-ii/description/

思路

dfs回溯。先对 candidates 进行排序。每次选定一个数字,然后 target 减去该数字,接着继续dfs。直到找到下一个数字刚好等于剩余target,此时刚好找到一种组合;如果下一个数字大于剩余target,则直接返回。
排序主要是为了方便剪枝。作用体现在两方面:

  1. 当 下一个数字大于剩余target时,再下一个数字也一定大于剩余target。
  2. 假如当前数字之前被选过了,即不是第一次选该数字,则也可以提前剪枝,避免重复组合。
  • 复杂度分析
    • 时间复杂度 O(2^n)。每个数字都有选或不选的可能。
    • 空间复杂度 O(n)。空间复杂度取决于递归的栈深度。

代码

class Solution {
public:
    vector<vector<int>> result;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> temp;
        backtrace(candidates, temp, 0, target);
        return result;
    }
    void backtrace(vector<int>& candidates, vector<int>& temp, int start, int target) {
        if (target == 0) {
            result.push_back(temp);
            return;
        }
        for (int i = start; i < candidates.size(); i++) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > target) {
                break;
            }
            temp.push_back(candidates[i]);
            backtrace(candidates, temp, i + 1, target - candidates[i]);
            temp.pop_back();
        }
    }
};

相关推荐

  1. leetcode 40. 组合总和 II

    2024-06-11 03:38:05       37 阅读
  2. LeetCode40. 组合总和 II

    2024-06-11 03:38:05       36 阅读
  3. leetcode_40.组合总和 II

    2024-06-11 03:38:05       9 阅读
  4. leetcode 40. 组合总和 II

    2024-06-11 03:38:05       6 阅读
  5. 40. 组合总和 II

    2024-06-11 03:38:05       30 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-06-11 03:38:05       8 阅读
  2. 【Python教程】压缩PDF文件大小

    2024-06-11 03:38:05       9 阅读
  3. 通过文章id递归查询所有评论(xml)

    2024-06-11 03:38:05       10 阅读

热门阅读

  1. Cordova WebView重定向到网站

    2024-06-11 03:38:05       5 阅读
  2. 重写setter方法要小心递归调用

    2024-06-11 03:38:05       4 阅读
  3. 代码随想录打卡第一天(补)

    2024-06-11 03:38:05       4 阅读
  4. web3规则改变者:Linea的厉害之处

    2024-06-11 03:38:05       5 阅读
  5. 什么是 prop drilling,如何避免?

    2024-06-11 03:38:05       7 阅读
  6. 【CSP】202312-1 仓库规划

    2024-06-11 03:38:05       6 阅读
  7. testbench仿真文件编写规则

    2024-06-11 03:38:05       6 阅读
  8. 头歌初识redis答案

    2024-06-11 03:38:05       4 阅读
  9. 机器人--矩阵运算

    2024-06-11 03:38:05       4 阅读
  10. 苹果智能:iOS 18 AI增强功能

    2024-06-11 03:38:05       5 阅读