LeetCode

ゝ一世哀愁。 2022-03-08 06:51 170阅读 0赞

## LeetCode78： ##

> 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。

\`\`\`  
输入: nums = \[1,2,3\]  
输出：\[\[\], \[1\], \[2\], \[2, 1\], \[3\], \[3, 1\], \[3, 2\], \[3, 2, 1\]\]  
\`\`\`  
大佬思路：直接从后遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集

\`\`\`  
def subsets(self, nums):  
        res=\[\[\]\]  
        for i in nums:  
            nres=res.copy()  
            for j in nres:  
                res.append(\[i\]+j)  
        return res  
\`\`\`  
ps:这个copy用的我服

## LeetCode 40 ##

### 回溯法终于搞明白了！！！ ###

> 给定一个数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。
> 
> `candidates` 中的每个数字在每个组合中只能使用一次。
> 
>     说明：解集不能包含重复的组合
>     输入: candidates = [10,1,2,7,6,1,5], target = 8,
>     所求解集为:
>     [
>       [1, 7],
>       [1, 2, 5],
>       [2, 6],
>       [1, 1, 6]
>     ]

class Solution:
        def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
            candidates.sort()
            result = []
            def permute(res,restart,target):
                if target == 0:
                    result.append(res)
                    return
                else:
                    index= restart
                    while index < len(candidates):
                        if candidates[index] > target:
                            break
                        else:
                            permute(res+[candidates[index]],index + 1,target - candidates[index])
                        while index < len(candidates) - 1 and candidates[index] == candidates[index + 1]:
                            index += 1
                        if index == len(candidates) - 1:
                            break
                        index += 1
            permute([],0,target)
            return result

当permute递归时break，不会跳出整个permute方法，只是跳出当前的递归，转而运行下面的

while index < len(candidates) - 1 and candidates[index] == candidates[index + 1]:

类似于树的递归求最大深度时，当前节点不符合要求，回溯到上一个节点继续递归。