题解 | #加起来和为目标值的组合#

用回溯法解决目标值组合问题

一、NC238 加起来和为目标值的组合

class Solution:
    def combinationCount(self , target: int, nums: List[int]) -> List[List[int]]:
        # write code here
        ''' 
        #元素不可以重复选取
        def dfs(track,start,target):
            if target==0:
                res.append(track.copy())
                return
            for i in range(start,len(nums)):
                track.append(nums[i])
                dfs(track,start+1,target-nums[i])
                track.pop()
        '''
        #元素可以重复选取
        def dfs(track,start,target):
            if target<0:
                return
            if target==0:
                res.append(track.copy())
                return
            for i in range(start,len(nums)):
                track.append(nums[i])
                #令start=i是为了避免出现例如这种情况：[[1,1,1,1,1],[1,4],[4,1],[5]]
                dfs(track,i,target-nums[i])
                track.pop()
                
        res,track = [], []
        dfs(track,0,target)
        return res                       

二、NC46 加起来和为目标值的组合(二)

class Solution:
    def combinationSum2(self , nums: List[int], target: int) -> List[List[int]]:
        # write code here
        def dfs(track,start,target):
            if target<0:
                return
            if target==0:
                res.append(track.copy())
                return
            for i in range(start,len(nums)):
                if i!=start and nums[i] == nums[i-1]:
                    continue
                track.append(nums[i])
                dfs(track,i+1,target-nums[i])
                track.pop()
                
        res,track = [], []
        nums.sort()
        dfs(track,0,target)
        return res

三、NC232 加起来和为目标值的组合(三)

class Solution:
    def combination(self , k: int, n: int) -> List[List[int]]:
        # write code here
        def dfs(track,start,target):
            if target < 0 or len(track)>k:
                return
            if target == 0 and len(track)==k:
                res.append(track.copy())
                return
            for i in range(start,10):
                track.append(i)
                dfs(track,i+1,target-i)
                track.pop()
        res,track = [], []
        dfs(track,1,n)
        return res

四、NC233 加起来和为目标值的组合(四)

class Solution:
    def combination(self , nums: List[int], target: int) -> int:
        # write code here
        def dfs(track,target):
            if target<0:
                return
            if target==0:
                res.append(track.copy())
                return
            for i in range(len(nums)):
                track.append(nums[i])
                dfs(track,target-nums[i])
                track.pop()
                
        res,track = [], []
        dfs(track,target)
        return len(res)