39 Combination Sum

https://leetcode.com/problems/combination-sum/

solution

(可以换一种问法，类似k-sum，给定array和target，返回全部可以总和到target的group)

• 有放回+控制重复。注意理解这里的需求，有放回是当下的元素可以无限取，但不能从过去元素取，否则造成结果重复。（元素可以重复，结果不能重复）

• 回溯时，每次的开始start仍然由i进行，小于0时进行剪枝（因此需要排序）

• 寻找某个target的dfs，都是target-item来递归。回溯是否需要再加回去？

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []
        candidates.sort()
        self.dfs(path, res, candidates, target, start=0)
        return res

    def dfs(self, path, res, candidates, target, start):
        if target < 0:  # 一定要有这步？
            return

        if target == 0:
            res.append(path[:])
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            self.dfs(path, res, candidates, target - candidates[i], i)  # 有放回i, 无放回i+1
            path.pop()

时间复杂度：O(candidates^target) 空间复杂度：O(target)

follow up

40. Combination Sum II

• 无放回，控制开始的index每次i+1，而不是i

• 控制重复，采用排序加剪枝。for循环横向遍历，对同一层使用过的元素跳过

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []
        start = 0
        candidates.sort(reverse=True)
        self.dfs(candidates, target, path, res, start)
        return res

    def dfs(self, candidates, target, path, res, start):
        if target < 0:
            return
        if target == 0:
            res.append(path[:])
            return

        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i-1]:  # 类似3sum中的控制重复
                continue
            path.append(candidates[i])
            self.dfs(candidates, target-candidates[i], path, res, i+1)
            path.pop()

时间复杂度：O(n⋅2^n) 空间复杂度：O(n+n⋅2^n)

216. Combination Sum III

• 不重复，开始从i+1

• 规定了选取的个数

# 第1个位置从9个选，第2个位置从8个选，但只能选到第k个位置. 因此决定时间复杂度
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        path = []
        res = []
        self.dfs(path, res, k, n, start=1)
        return res

    def dfs(self, path, res, k, residual, start):
        if len(path) == k and residual == 0:
            res.append(path.copy())
            return

        for i in range(start, 10):
            path.append(i)
            residual -= i
            self.dfs(path, res, k, residual, i+1)
            path.pop(-1)
            residual += i

时间复杂度：O(9! / (9 - k)!) 空间复杂度：O(C(9, k))

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        path = []
        res = []
        start = 1
        return self.dfs(path, res, k, n, start)

    def dfs(self, path, res, k, n, start):
        if len(path) == k and sum(path) == n:
            res.append(path[:])

        for i in range(start, 10):
            path.append(i)
            self.dfs(path, res, k, n, i+1)
            path.pop()
        return res

时间复杂度：O() 空间复杂度：O()

377. Combination Sum IV

494. Target Sum

• 动态规划/背包

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)
        if abs(target) > total_sum:
            return 0
        if (target + total_sum) % 2 == 1:
            return 0
        
        target_sum = (total_sum + target) // 2
        dp = [0] * (target_sum + 1)
        dp[0] = 1

        for i in nums:
            for j in range(target_sum, i-1, -1):
                dp[j] += dp[j-i]
        return dp[target_sum]

473. Matchsticks to Square

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        sticks_sum = sum(matchsticks)
        if sticks_sum % 4 != 0:
            return False
        
        line = sticks_sum // 4

        matchsticks.sort(reverse = True)
        edges = [0] * 4
        return self.dfs(0, matchsticks, edges, line)
    
    def dfs(self, idx, matchsticks, edges, line):
        if idx == len(matchsticks):
            return True
        
        for edge in range(4):
            if edge > 0 and edges[edge] == edges[edge-1]:
                continue
            
            edges[edge] += matchsticks[idx]
            if edges[edge] <= line and self.dfs(idx + 1, matchsticks, edges, line):
                return True
            
            edges[edge] -= matchsticks[idx]
        return False