【leetcode】组合总和 II

红太狼 2022-03-11 10:10 250阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

思路：  
首先对数组进行排序  
采用递归，递归分为两种，第一种是考虑这个元素，第二种是不考虑这个元素，因此使用递归起来就很方便，如果和大于target，那么说明后面的数字已经不需要考虑了，直接剪枝即可。这儿需要用到回溯的思想。

class Solution:
        def __init__(self):
            self.results = []
        def Recursion(self, nums, index, target, total, result):
            if index >= len(nums):
                return
            if nums[index] + total == target:
                result.append(nums[index])
                if result not in self.results:
                    self.results.append(result)
            elif nums[index] + total < target:
                temp = result[:]
                result.append(nums[index])
                self.Recursion(nums, index + 1, target, total + nums[index], result)
                result = temp[:]
                self.Recursion(nums, index + 1, target, total, result)
        def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
            if candidates == []:
                return []
            nums = sorted(candidates)
            self.Recursion(nums, 0, target, 0, [])
            return self.results

![在这里插入图片描述][20190307201341316.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220311/bb9a8415a168443dabbe4435ce461310.png
[20190307201341316.png]: /images/20220311/8920a9d822734e38bf2db256c0e14c21.png

发表评论取消回复

表情：

评论列表（有 0 条评论，250人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-40.组合总和II

目录题目思路回溯法题目来源 [40.组合总和II][40._II] 题目思路这道题目和39.组合总和如下区别：本

曾经终败给现在/ 2024年03月26日 12:18/ 0 赞/ 93 阅读

相关 leetcode 40. 组合总和 II

利用set去重，一维vector判断相等需要都按照一种顺序排好超时 class Solution { public: vector<v

逃离我推掉我的手/ 2023年06月08日 06:19/ 0 赞/ 15 阅读

相关【LeetCode 40】组合总和 II

题目描述给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidate

刺骨的言语ヽ痛彻心扉/ 2022年12月05日 13:55/ 0 赞/ 156 阅读

相关 LeetCode 40. 组合总和 II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

怼烎@/ 2022年11月01日 15:59/ 0 赞/ 207 阅读

相关 LeetCode40. 组合总和 II

给定一个数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。 `candidat

ゝ一世哀愁。/ 2022年05月14日 05:47/ 0 赞/ 189 阅读

相关 LeetCode 【40.组合总和 II】

LeetCode 【40.组合总和 II】题目描述：给定一个数组`candidates`和一个目标数`target`,找出`candidates`中所有可以使数字

冷不防/ 2022年04月13日 14:53/ 0 赞/ 237 阅读

相关 leetcode:40. 组合总和 II

题目连接: [https://leetcode-cn.com/problems/combination-sum-ii/description/][https_leetcod

客官°小女子只卖身不卖艺/ 2022年04月13日 02:23/ 0 赞/ 246 阅读

相关【leetcode】组合总和 II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

红太狼/ 2022年03月11日 10:10/ 0 赞/ 251 阅读

相关 leetcode:40.组合总和 II

题目描述：给定一个数组 `candidates`和一个目标数 `target`，找出 `candidates`中所有可以使数字和为 `target`的组合。 `can

迷南。/ 2022年02月16日 17:07/ 0 赞/ 274 阅读

相关 LeetCode-40.组合总和II

题目给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates

骑猪看日落/ 2022年01月25日 22:35/ 0 赞/ 267 阅读