Backtracking

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

Backtrackingをちゃんと理解できればDPも書けるのでかなり大事。

105. Subsets

Problem

Given an array nums of unique integers, return all possible subsets of nums.

The solution set must not contain duplicate subsets. You may return the solution in any order.

Example 1:

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Copy

Example 2:

Input: nums = [7]

Output: [[],[7]]

Copy

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

Solution

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []

        def dfs(i: int) -> None:
            if i == len(nums):
                res.append(subset.copy())
                return
            
            # pick
            subset.append(nums[i])
            dfs(i+1)

            # not pick
            subset.pop()
            dfs(i+1)
        
        dfs(0)
        return res

106. Combination Sum

Problem

You are given an array of distinct integers nums and a target integer target. Your task is to return a list of all unique combinations of nums where the chosen numbers sum to target.

The same number may be chosen from nums an unlimited number of times. Two combinations are the same if the frequency of each of the chosen numbers is the same, otherwise they are different.

You may return the combinations in any order and the order of the numbers in each combination can be in any order.

Example 1:

Input: 
nums = [2,5,6,9] 
target = 9

Output: [[2,2,5],[9]]

Copy

Explanation:
2 + 2 + 5 = 9. We use 2 twice, and 5 once.
9 = 9. We use 9 once.

Example 2:

Input: 
nums = [3,4,5]
target = 16

Output: [[3,3,3,3,4],[3,3,5,5],[4,4,4,4],[3,4,4,5]]

Copy

Example 3:

Input: 
nums = [3]
target = 5

Output: []

Copy

Constraints:

• All elements of nums are distinct.
• 1 <= nums.length <= 20
• 2 <= nums[i] <= 30
• 2 <= target <= 30

Solution

class Solution:
    def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        subset = []

        def dfs(i: int, total: int) -> None:
            if total == target:
                res.append(subset.copy())
                return
            
            if total > target or i == len(nums):
                return
            
            # pick and stay
            subset.append(nums[i])
            dfs(i, total + nums[i])

            # not pick and go
            # (pick and goは、pick and stayの後にnot pick and goで良い)
            subset.pop()
            dfs(i+1, total)
        
        dfs(0, 0)
        return res

107. Permutations

Problem

Given an array nums of unique integers, return all the possible permutations. You may return the answer in any order.

Example 1:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Copy

Example 2:

Input: nums = [7]

Output: [[7]]

Copy

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10

Solution

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 1:
            return [nums.copy()]
        
        res = []
        perms = self.permute(nums[1:])
        for perm in perms:
            for j in range(len(perm)+1):
                perm_copy = perm.copy()
                perm_copy.insert(j, nums[0])
                res.append(perm_copy)
        
        return res

108. Subsets II

Problem

Given an array nums of unique integers, return all the possible permutations. You may return the answer in any order.

Example 1:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Copy

Example 2:

Input: nums = [7]

Output: [[7]]

Copy

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10

Solution

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        subset = []
        res = []

        def dfs(i: int) -> None:
            if i == len(nums):
                res.append(subset.copy())
                return
            
            # pick
            subset.append(nums[i])
            dfs(i+1)

            # skip duplicate value
            while i+1 < len(nums) and nums[i] == nums[i+1]:
                i += 1

            # not pick
            subset.pop()
            dfs(i+1)
        
        dfs(0)
        return res

109. Combination Sum II

Problem

You are given an array of integers nums, which may contain duplicates, and a target integer target. Your task is to return a list of all unique combinations of nums where the chosen numbers sum to target.

Each element from nums may be chosen at most once within a combination. The solution set must not contain duplicate combinations.

You may return the combinations in any order and the order of the numbers in each combination can be in any order.

Example 1:

Input: candidates = [9,2,2,4,6,1,5], target = 8

Output: [
  [1,2,5],
  [2,2,4],
  [2,6]
]

Copy

Example 2:

Input: candidates = [1,2,3,4,5], target = 7

Output: [
  [1,2,4],
  [2,5],
  [3,4]
]

Copy

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

Solution

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()

        res = []
        subset = []

        def dfs(i: int, total: int) -> None:
            if total == target:
                res.append(subset.copy())
                return
            
            if total > target or i == len(candidates):
                return
            
            # pick
            subset.append(candidates[i])
            dfs(i+1, total + candidates[i])

            # skip duplicate
            while i+1 < len(candidates) and candidates[i] == candidates[i+1]:
                i+=1

            # not pick
            subset.pop()
            dfs(i+1, total)
        
        dfs(0, 0)
        return res

110. Word Search

Problem

Given a 2-D grid of characters board and a string word, return true if the word is present in the grid, otherwise return false.

For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Example 1:

Input: 
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "CAT"

Output: true

Copy

Example 2:

Input: 
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "BAT"

Output: false

Copy

Constraints:

• 1 <= board.length, board[i].length <= 5
• 1 <= word.length <= 10
• board and word consists of only lowercase and uppercase English letters.

Solution

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]
        visited = set()

        def dfs(r: int, c: int, word_i: int) -> True:
            if word_i == len(word):
                return True
            
            if (r not in range(ROWS) or
                c not in range(COLS) or
                (r,c) in visited or
                board[r][c] != word[word_i]
                ):
                return False
            
            visited.add((r,c))
            for dr, dc in DIRECTIONS:
                nr, nc = dr + r, dc + c
                if dfs(nr, nc, word_i + 1):
                    return True

            visited.remove((r,c))
            
            return False
        
        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r, c, 0):
                    return True
        
        return False
        

111. Palindrome Partitioning

Problem

Given a string s, split s into substrings where every substring is a palindrome. Return all possible lists of palindromic substrings.

You may return the solution in any order.

Example 1:

Input: s = "aab"

Output: [["a","a","b"],["aa","b"]]

Copy

Example 2:

Input: s = "a"

Output: [["a"]]

Copy

Constraints:

• 1 <= s.length <= 20
• s contains only lowercase English letters.

Solution

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        subset = []

        def isPalin(l: int, r: int, s: str) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        def dfs(i: int) -> None:
            if i == len(s):
                res.append(subset.copy())
                return
            
            for j in range(i, len(s)):
                if isPalin(i, j, s):
                    subset.append(s[i:j+1])
                    dfs(j+1)
                    subset.pop()
        dfs(0)
        return res

112. Letter Combinations of a Phone Number

Problem

You are given a string digits made up of digits from 2 through 9 inclusive.

Each digit (not including 1) is mapped to a set of characters as shown below:

A digit could represent any one of the characters it maps to.

Return all possible letter combinations that digits could represent. You may return the answer in any order.

Example 1:

Input: digits = "34"

Output: ["dg","dh","di","eg","eh","ei","fg","fh","fi"]

Copy

Example 2:

Input: digits = ""

Output: []

Copy

Constraints:

• 0 <= digits.length <= 4
• 2 <= digits[i] <= 9

Solution

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        
        digit_alpha_map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }

        res = []
        subset = []

        def dfs(i: int) -> None:
            if i == len(digits):
                subset_copy = subset.copy()
                res.append(''.join(subset_copy))
                return
            
            for c in digit_alpha_map[digits[i]]:
                subset.append(c)
                dfs(i+1)
                subset.pop()
        
        dfs(0)
        return res

113. N Queens

Problem

You are given a string digits made up of digits from 2 through 9 inclusive.

Each digit (not including 1) is mapped to a set of characters as shown below:

A digit could represent any one of the characters it maps to.

Return all possible letter combinations that digits could represent. You may return the answer in any order.

Example 1:

Input: digits = "34"

Output: ["dg","dh","di","eg","eh","ei","fg","fh","fi"]

Copy

Example 2:

Input: digits = ""

Output: []

Copy

Constraints:

• 0 <= digits.length <= 4
• 2 <= digits[i] <= 9

Solution

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        rows = set()
        cols = set()
        diago_plus = set()
        diago_minus = set()

        res = []
        board = [['.'] * n for _ in range(n)]

        def dfs(r: int) -> None:
            if r == n:
                tmp = []
                for i in range(n):
                    tmp.append(''.join(board[i]))
                res.append(tmp)
                return
            
            for c in range(n):
                if (r in rows or
                    c in cols or
                    r-c in diago_plus or
                    r+c in diago_minus
                    ):
                    continue
                
                board[r][c] = 'Q'
                rows.add(r)
                cols.add(c)
                diago_plus.add(r-c)
                diago_minus.add(r+c)

                dfs(r+1)

                board[r][c] = '.'
                rows.remove(r)
                cols.remove(c)
                diago_plus.remove(r-c)
                diago_minus.remove(r+c)

        dfs(0)
        return res