Leetcode 40/216

Posted on | | 阅读数
Words count in article: 160 | Reading time ≈ 1

Question1

Solution

Dfs。需要注意的是相同的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []
        candidates.sort()
        self.dfs(candidates, target, [], results)
        return results
    
    
    def dfs(self, candidates, target, temp, results):
        if target < 0:
            return 
        if target == 0:
            results.append(temp)
        for i in range(len(candidates)):
            if i != 0 and candidates[i] == candidates[i-1]:
                continue
            self.dfs(candidates[i+1:], target - candidates[i], temp + [candidates[i]], results)

Question2

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        results = []
        nums = list(range(1, 10))
        self.dfs(0, nums, k, n, [], results)
        return results
    
    def dfs(self, index, nums, k, n, temp, results):
        if k < 0 or n < 0:
            return 
        if k == 0 and n == 0:
            results.append(temp)
        
        for i in range(index, len(nums)):
            self.dfs(i+1, nums, k-1, n-nums[i], temp+[nums[i]], results)