全排列

46. 全排列
给定一个不含重复数字的数组 nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

  1. # 输入: nums = [1, 2, 3]
  2. # 输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
  3. class Solution:
  4.     def permute(self, nums):
  5.         result_all = []
  6.         visited = [0] * len(nums)
  8.         def dfs(n, nums, result):
  9.             if n == len(nums):
  10.                 result_all.append(result[:])
  11.             for i in range(len(nums)):
  12.                 if visited[i] == 1:
  13.                     continue
  14.                 result.append(nums[i])
  15.                 visited[i] = 1
  16.                 dfs(n+1, nums, result)
  17.                 result.pop()
  18.                 visited[i] = 0
  19.         dfs(0, nums, [])
  20.         return result_all

47. 全排列 II
给定一个可包含重复数字的序列 nums，按任意顺序 返回所有不重复的全排列。

  1. # 输入: nums = [1, 1, 2]
  2. # 输出: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
  3. class Solution:
  4.     def permuteUnique(self, nums):
  5.         result_all = []
  6.         visited = [0] * len(nums)
  7.         nums.sort()
  9.         def dfs(n, nums, result):
  10.             if n == len(nums):
  11.                 result_all.append(result[:])
  12.             for i in range(len(nums)):
  13.                 if visited[i] == 1:
  14.                     continue
  15.                 if i > 0 and nums[i] == nums[i-1] and visited[i-1]==0:
  16.                     continue
  17.                 result.append(nums[i])
  18.                 visited[i] = 1
  19.                 dfs(n+1, nums, result)
  20.                 result.pop()
  21.                 visited[i] = 0       
  22.         dfs(0, nums, [])
  23.         return result_all

组合总和

39. 组合总和
给定一个无重复元素的正整数数组 candidates 和一个正整数 target，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 

  1. # 输入: candidates = [2, 3, 6, 7], target = 7
  2. # 输出: [[7], [2, 2, 3]]
  3. class Solution:
  4.     def combinationSum(self, candidates, target):
  5.         result_all = []
  7.         def dfs(n, nums, result, start_id, target):
  8.             if target == 0:
  9.                 result_all.append(result[:])
  10.             for i in range(start_id, len(nums)):
  11.                 if nums[i] > target:
  12.                     continue
  13.                 result.append(nums[i])
  14.                 dfs(n+1, nums, result, i, target-nums[i])
  15.                 result.pop()
  16.         dfs(0, candidates, [], 0, target)
  17.         return result_all

40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

  1. # 输入: candidates = [2, 5, 2, 1, 2], target = 5
  2. # 输出: [[1, 2, 2], [5]]
  3. class Solution:
  4.     def combinationSum2(self, candidates, target):
  5.         result_all = []
  6.         visited = [0] * len(candidates)
  7.         candidates.sort()
  9.         def dfs(n, nums, result, target, start_id):
  10.             if target == 0:
  11.                 result_all.append(result[:])
  12.             for i in range(start_id, len(nums)):
  13.                 if visited[i] == 1:
  14.                     continue
  15.                 if nums[i] > target:
  16.                     continue
  17.                 if i>0 and nums[i]==nums[i-1] and visited[i-1]==0:
  18.                     continue
  19.                 result.append(nums[i])
  20.                 visited[i] = 1
  21.                 dfs(n+1, nums, result, target-nums[i], i)
  22.                 result.pop()
  23.                 visited[i] = 0
  25.         dfs(0, candidates, [], target, 0)
  26.         return result_all

216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：

  • 所有数字都是正整数。

  • 解集不能包含重复的组合。 

    1. # 输入: k = 3, n = 7
    2. # 输出: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
    3. class Solution:
    4.   def combinationSum3(self, k, n):
    5.       result_all = []
    6.       visited = [0] * 9
    7.       def dfs(_n, result, target, start_id):
    8.           if target == 0 and len(result)==k:
    9.               result_all.append(result[:])
    10.           for i in range(start_id, 9):
    11.               if visited[i] == 1:
    12.                   continue
    13.               if (i+1) > target:
    14.                   continue
    15.               if len(result) > k:
    16.                   continue
    17.               result.append(i+1)
    18.               visited[i] = 1
    19.               dfs(_n+1, result, target-(i+1), i)
    20.               result.pop()
    21.               visited[i] = 0
    23.       dfs(0, [], n, 0)
    24.       return result_all

    深度优先搜索

    79. 单词搜索

    1. class Solution:
    2.   def exist(self, board: List[List[str]], word: str) -> bool:
    3.       m, n = len(board), len(board[0])
    4.       directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    5.       visited = set()
    7.       def dfs(i, j, k):
    8.           if board[i][j] != word[k]:  # 不匹配
    9.               return False
    10.           if k == len(word)-1:
    11.               return True
    12.           visited.add((i, j))
    13.           result = False
    14.           for di, dj in directions:
    15.               newi, newj = i+di, j+dj
    16.               if 0 <= newi < len(board) and 0 <= newj < len(board[0]):  # 不越界
    17.                   if (newi, newj) not in visited:  # 未访问
    18.                       if dfs(newi, newj, k+1):
    19.                           result = True
    20.                           break
    21.           visited.remove((i, j))
    22.           return result
    24.       for _m in range(m):
    25.           for _n in range(n):
    26.               if dfs(_m, _n, 0):
    27.                   return True
    28.       return False