搜索Tag部分

这部分主要用来记录总结Leetcode中数组部分的题目和思路分析

语言：python

NO.39 Combination Sum

题目

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

Example 1:
1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
Example 2:
1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

解题思路

这道题是搜索类题目，需要用到DFS。

DFS其实是一个递归的过程，对于所有的递归过程我们需要知道的是停止的点，以及边界的变化。这个组合数求和的题目终止的点就是当所加数之和大于target或者等于target的时候。更新的部分应该就是target的变化，以及path的变化。

几个值得注意的地方：

什么时候变化target？
什么时候更新path？

在做下次的变化的时候同时跟新target和path

def dfs(nums, idx, target, path, sol):
  if target == 0: 
    sol.append(path)
    return 
  if target < 0:
    return
  for i in range(idx, len(nums)):
    dfs(nums, i , target - nums[i], path + [nums[i]], sol)

需要用到动态规划：

Solution

def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        sol = []
        candidates.sort()
        self.dfs(candidates, 0, [], sol, target)
        
        return sol
        
    def dfs(self, nums, idx, path, sol, target):
        
        if target == 0:
            sol.append(path)
            return
        if target < 0:
            return
        
        for i in range(idx, len(nums)):
            self.dfs(nums, i, path + [nums[i]], sol, target - nums[i])

光

Algorithm | Leetcode - search

搜索Tag部分

NO.39 Combination Sum

题目

解题思路

Solution