# Graph Depth First Search

## 1. Split String

Give a string, you can choose to split the string after one character or two adjacent characters, and make the string to be composed of only one character or two characters. Output all possible results.

`Input: "123"Output: [["1","2","3"],["12","3"],["1","23"]]`
`Input: "12345"Output: [["1","23","45"],["12","3","45"],["12","34","5"],["1","2","3","45"],["1","2","34","5"],["1","23","4","5"],["12","3","4","5"],["1","2","3","4","5"]]`
`def splitString(self, s):        res = []        self.backtrack(s, 0, [], res)        return res        def backtrack(self, s, i, ans, res):        if i == len(s):            res.append(ans[:])            return                for j in range(1, 3):            if i + j <= len(s):                num = s[i:i+j]                ans.append(num)                self.backtrack(s, i + j, ans, res)                ans.pop()`

## 2. Letter Combinations of a Phone Number

Given a digit string excluded `'0'` and `'1'`, return all possible letter combinations that the number could represent.

`Input: "23"Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]Explanation: '2' could be 'a', 'b' or 'c''3' could be 'd', 'e' or 'f'`
`Input: "5"Output: ["j", "k", "l"]`
`class Solution:    KEYBOARD = {    '2': 'abc',    '3': 'def',    '4': 'ghi',    '5': 'jkl',    '6': 'mno',    '7': 'pqrs',    '8': 'tuv',    '9': 'wxyz',    }    def letterCombinations(self, digits):        result = []        if not digits:            return result        self.dfs(digits, 0, [], result)        return result        def dfs(self, digits, i, ans, result):        if i == len(digits):            result.append(''.join(ans))            return                for letter in Solution.KEYBOARD[digits[i]]:            ans.append(letter)             self.dfs(digits, i + 1, ans, result)            ans.pop()`

## 3. Combination Sum II

Given an array `num` and a number `target`. Find all unique combinations in `num` where the numbers sum to `target`.

• Each number in `num` can only be used once in one combination.
• All numbers (including `target`) will be positive integers.
• Numbers in a combination `a1, a2, … , ak` must be in non-descending order. (ie, `a1 ≤ a2 ≤ … ≤ ak`)
• Different combinations can be in any order.
• The solution set must not contain duplicate combinations.
`Input: num = [7,1,2,5,1,6,10], target = 8Output: [[1,1,6],[1,2,5],[1,7],[2,6]]`
`Input: num = [1,1,1], target = 2Output: [[1,1]]Explanation: The solution set must not contain duplicate combinations.`
`class Solution:    def combinationSum2(self, num, target):        num = sorted(num)               results, ans, visited = [], [], [False] * len(num)                self.dfs(num, target, 0, 0, visited, ans, results)                return results        def dfs(self, num, target, start, now, visited, ans, results):                if now == target:                        return results.append(ans[:])                                for i in range(start, len(num)):                        if now + num[i] <= target and (i == 0 or num[i] != num[i-1] or visited[i- 1] == True):                      ans.append(num[i])                visited[i] = True                                self.dfs(num, target, i+1, now + num[i], visited, ans, results)                                ans.pop()                                visited[i] = 0`

## 4. Combination Sum

Given a set of candidtate numbers `candidates` and a target number `target`. Find all unique combinations in `candidates` where the numbers sums to `target`.

• All numbers (including `target`) will be positive integers.
• Numbers in a combination `a1, a2, … , ak` must be in non-descending order. (ie, `a1 ≤ a2 ≤ … ≤ ak`)
• Different combinations can be in any order.
• The solution set must not contain duplicate combinations.
`Input: candidates = [2, 3, 6, 7], target = 7Output: [, [2, 2, 3]]`
`Input: candidates = , target = 3Output: [[1, 1, 1]]`
`def combinationSum(self, candidates, target):        candidates = sorted(list(set(candidates)))        result = []        self.dfs(candidates, target, 0, [], result)        return result            def dfs(self, candidates, target, start, ans, result):        if target < 0:            return         if target == 0:            return result.append(ans[:])                             for i in range(start, len(candidates)):            ans.append(candidates[i])            self.dfs(candidates, target - candidates[i], i, ans, result)            ans.pop()`

## 5. N-Queens

The n-queens puzzle is the problem of placing n queens on an `n×n` chessboard such that no two queens attack each other(Any two queens can't be in the same row, column, diagonal line).

`Input:1Output:   [["Q"]]`
`Input:4Output:[  // Solution 1  [".Q..",   "...Q",   "Q...",   "..Q."  ],  // Solution 2  ["..Q.",   "Q...",   "...Q",   ".Q.."  ]]`
`class Solution:    def solveNQueens(self, n):        boards = []        visited = {            'col': set(),            'sum': set(),            'diff': set(),        }        self.dfs(n, [], visited, boards)        return boards            def dfs(self, n, permutation, visited, boards):        if n == len(permutation):            boards.append(self.draw(permutation))            return                row = len(permutation)        for col in range(n):            if not self.is_valid(permutation, visited, col):                continue            permutation.append(col)            visited['col'].add(col)            visited['sum'].add(row + col)            visited['diff'].add(row - col)            self.dfs(n, permutation, visited, boards)            visited['col'].remove(col)            visited['sum'].remove(row + col)            visited['diff'].remove(row - col)            permutation.pop()# O(1)    def is_valid(self, permutation, visited, col):        row = len(permutation)        if col in visited['col']:            return False        if row + col in visited['sum']:            return False        if row - col in visited['diff']:            return False        return True            def draw(self, permutation):        board = []        n = len(permutation)        for col in permutation:            row_string = ''.join(['Q' if c == col else '.' for c in range(n)])            board.append(row_string)        return board`
• Each element in a subset must be in non-descending order.
• The ordering between two subsets is free.
• The solution set must not contain duplicate subsets.
`Input: Output:[  [],  ]`
`Input: [1,2,2]Output:[  ,  ,  [1,2,2],  [2,2],  [1,2],  []]`
`class Solution:    def subsetsWithDup(self, nums):        if not len(nums):            return [[]]                nums.sort()                res = []        self.dfs(nums, 0, None, [], res)        return res            def dfs(self, nums, i, prev, ans, res):        #print('i', i, 'prev', prev, 'ans', ans)        if i == len(nums):            res.append(ans[:])            return                if i - 1 >= 0 and nums[i] == nums[i-1]:            if prev == i - 1:                ans.append(nums[i])                self.dfs(nums, i + 1, i, ans, res)                ans.pop()        else:            ans.append(nums[i])            self.dfs(nums, i + 1, i, ans, res)            ans.pop()                    self.dfs(nums, i + 1, prev, ans, res)`

## 7. Subsets

Given a set of distinct integers, return all possible subsets.

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.
`Input: Output:[  [],  ]`
`Input: [1,2,3]Output:[  ,  ,  ,  [1,2,3],  [1,3],  [2,3],  [1,2],  []]`
`class Solution:    def subsets(self, nums):        nums = sorted(nums)        results = []        self.dfs(nums, 0, [], results)        return results            def dfs(self, nums, start, subset, results):         results.append(subset[:])         for i in range(start, len(nums)):             subset.append(nums[i])             self.dfs(nums, i + 1, subset, results)             subset.pop()`

## 8. Permutations

Given a list of numbers, return all possible permutations.

# Example

Example 1:

`Input: Output:[  ]`
`Input: [1,2,3]Output:[  [1,2,3],  [1,3,2],  [2,1,3],  [2,3,1],  [3,1,2],  [3,2,1]]`
`class Solution:    def permute(self, nums):        visited = [False] * len(nums)                results = []        self.permutations(nums, visited, [], results)        return results            def permutations(self, nums, visited, ans, results):        lenth = len(nums)        if len(ans) == len(nums):            return results.append(ans[:])                for i in range(0, lenth):            if visited[i]:                continue            ans.append(nums[i])            visited[i] = True            self.permutations(nums, visited, ans, results)            visited[i] = False            ans.pop()`

## 9. Word Pattern II

Given a `pattern` and a string `str`, find if `str` follows the same pattern.

`Input:pattern = "abab"str = "redblueredblue"Output: trueExplanation: "a"->"red","b"->"blue"`
`Input:pattern = "aaaa"str = "asdasdasdasd"Output: trueExplanation: "a"->"asd"`
`Input:pattern = "aabb"str = "xyzabcxzyabc"Output: false`
`class Solution:    def wordPatternMatch(self, pattern, str):        return self.is_match(pattern, str, {}, set())def is_match(self, pattern, string, mapping, used):        if not pattern:            return not string                    char = pattern        if char in mapping:            word = mapping[char]            if not string.startswith(word):                return False            return self.is_match(pattern[1:], string[len(word):], mapping, used)                    for i in range(len(string)):            word = string[:i + 1]            if word in used:                continue                        used.add(word)            mapping[char] = word                        if self.is_match(pattern[1:], string[i + 1:], mapping, used):                return True                        del mapping[char]            used.remove(word)                    return False`

## 10. Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, output sequence in dictionary order.
Transformation rule such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• At least one solution exists.
`Input：start = "a"，end = "c"，dict =["a","b","c"]Output：[["a","c"]]Explanation："a"->"c"`
`Input：start ="hit"，end = "cog"，dict =["hot","dot","dog","lot","log"]Output：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]Explanation：1."hit"->"hot"->"dot"->"dog"->"cog"2."hit"->"hot"->"lot"->"log"->"cog"The dictionary order of the first sequence is less than that of the second.`
`from collections import dequeclass Solution:    def findLadders(self, start, end, dict):        dict.add(start)        dict.add(end)        distance = {}                self.bfs(end, distance, dict)                results = []        self.dfs(start, end, distance, dict, [start], results)                return resultsdef bfs(self, start, distance, dict):        distance[start] = 0        queue = deque([start])        while queue:            word = queue.popleft()            for next_word in self.get_next_words(word, dict):                if next_word not in distance:                    distance[next_word] = distance[word] + 1                    queue.append(next_word)        def get_next_words(self, word, dict):        words = []        for i in range(len(word)):            for c in 'abcdefghijklmnopqrstuvwxyz':                next_word = word[:i] + c + word[i + 1:]                if next_word != word and next_word in dict:                    words.append(next_word)        return words                            def dfs(self, curt, target, distance, dict, path, results):        if curt == target:            results.append(list(path))            return                for word in self.get_next_words(curt, dict):            if distance[word] != distance[curt] - 1:                continue            path.append(word)            self.dfs(word, target, distance, dict, path, results)            path.pop()`

--

--