backtracking

*backtracking.py

Combination.py

https://leetcode.com/problemset/all/?search=Combination%20Sum
candidates without duplicates: 39 / 
                                      78 sub sets / 254. Factor Combinations
                                                  
candidates with duplicates: 40 / 267. Palindrome Permutation II
combinations of k numbers: 216
output number of possible combinations:  377 
others： 10. Regular Expression Matching / 294. Flip Game II / 291. Word Pattern II / 51. N-Queens /52. N-Queens II / 351. Android Unlock Patterns
  
39. Combination Sum (candidates without duplicates)  *
https://leetcode.com/problems/combination-sum/description/
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:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        #runtime complexity: O(N!) space complexity: O(N)
        
        def dfs(candidates, target, sublist):
            if target==0: ans.append(sublist)
            if target > 0:
                for i, num in enumerate(candidates):
                    dfs(candidates[i:], target-num, sublist+[num])
            
        ans= []
        dfs(candidates, target, [])
        return ans
#-------------------------------------------------------------------------------------------
40. Combination Sum II (candidates with duplicates)
https://leetcode.com/problems/combination-sum-ii/description/
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

#runtime complexity: O(m*log(m) + n!) space complexity: O(m)  m=len(candidates)  n=len(set(candidates))

def dfs(candidates, target, sublist):
    if target==0:   ans.append(sublist)

    if target > 0:
        last= None
        for i, num in enumerate(candidates):
            if last==num: continue
            last= num
            dfs(candidates[i+1:], target-num, sublist+[num])

ans= []
candidates.sort()
dfs(candidates, target, [])
return ans

#---------------------------------------------------------------------------------------------------
216. Combination Sum III
https://leetcode.com/problems/combination-sum-iii/description/
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]
  
def dfs(nums, k, target, sublist):
    if k==0 and target==0:
        ans.append(sublist)

    if k > 0 and target>0:
        for i, num in enumerate(nums):
            dfs(nums[i+1:], k-1, target-num, sublist+[num])

nums= range(1, 10)
ans= []
dfs(nums, k, n ,[])
return ans  
 
#---------------------------------------------------------------------------------------------
377. Combination Sum IV
https://leetcode.com/problems/combination-sum-iv/description/
  
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.  
nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.
Therefore the output is 7.

#---------------------------------------------------------------------------------------
Others
51. N-Queens /52. N-Queens II
https://leetcode.com/problems/n-queens/
Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
class Solution {
    List<List<String>> ans= new ArrayList<List<String>>();
    
	Set<Integer> cols= new HashSet<>();
	Set<Integer> diagonal1= new HashSet<>();
	Set<Integer> diagonal2= new HashSet<>();
    int[][] board;

    public List<String> toList(int N){
        List<String> list= new ArrayList<>();
        for(int i=0; i<N; i++){
            String str="";
            for(int j=0; j<N; j++){
                if(board[i][j]==0) str += ".";
                else str +="Q";
            }
            list.add(str);
        }
        return list;
    }
    
    
	public void dfs(int row, int N) {
		for(int col=0; col<N; col++) {
			if(row==N) {
                ans.add( toList(N) );
				return;
			}
			
			int diag1= row-col, diag2= row+col;
			if ( cols.contains(col) || diagonal1.contains(diag1) || diagonal2.contains(diag2) ) continue;

			cols.add(col);
			diagonal1.add(diag1);
			diagonal2.add(diag2);
			board[row][col]= 1;

			dfs(row+1, N);
			
			cols.remove(col);
			diagonal1.remove(diag1);
			diagonal2.remove(diag2);
			board[row][col]= 0;
		}
	}    
    
    public List<List<String>> solveNQueens(int n) {
       	board= new int[n][n];
		dfs(0, n); 
        return ans;
    }
}
      
547. Friend Circles
https://leetcode.com/problems/friend-circles/description/
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. 
For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. 
And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, 
then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number 
of friend circles among all the students.
Example 1:
Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
class Solution(object):
    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """ 
        #runtime complexity O(n**2) space complexity O(n)   n= Len(M)
        def dfs(i):
            if used[i]==False:
                used[i]= True
                for j in range(Len):
                    if M[i][j]==1: dfs(j) 
                return True
        
        if not M:   return 0
        Len= len(M)
        used= Len*[False]
        return sum( dfs(i)==True for i in range(Len)) 

combination_sequence.py

425. Word Squares
https://leetcode.com/problems/word-squares/description/
Given a set of words (without duplicates), find all word squares you can build from them.
A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).
For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.
b a l l
a r e a
l e a d
l a d y
Note:
There are at least 1 and at most 1000 words.
All words will have the exact same length.
Word length is at least 1 and at most 5.
Each word contains only lowercase English alphabet a-z

Islands.py

https://leetcode.com/problemset/algorithms/?search=island
count of islands: 200,305,694,711  
max area of island: 695,827
other(Perimeter): 463

200. Number of Islands
https://leetcode.com/problems/number-of-islands/
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Input:
        11000
        11000
        00100
        00011
Output: 3

runtime complexity: O(h*w)  space complexity: O(2)
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        def dfs(i, j):
            if 0<=i<h and 0<=j<w and grid[i][j]=='1': 
                grid[i][j]=False
                dfs(i+1,j)
                dfs(i-1,j)
                dfs(i,j+1)
                dfs(i,j-1)
                return True
            
        if not len(grid):   return 0
        h, w= len(grid), len(grid[0])
        ans = 0
        for i in range(h):   
            for j in range(w):
                ans += dfs(i, j)>0 
        return ans

#----------------------------------------------------------------------------------------------------------



#--------------------------------------------------------------------------------------
694. Number of Distinct Islands
https://leetcode.com/problems/number-of-distinct-islands/description/
Example 1:
11000
11000
00011
00011
Given the above grid map, return 1.
Example 2:
11011
10000
00001
11011
Given the above grid map, return 3.

def normalize(island):
    island.sort()
    origin= island[0][0], island[0][1]
    for p in island:
        p[0] -= origin[0]
        p[1] -= origin[1]
    return island
#--------------------------------------------------------------------------------
711. Number of Distinct Islands II
https://leetcode.com/problems/number-of-distinct-islands/description/
Example 1:
11000
10000
00001
00011
Given the above grid map, return 1. 

Notice that:
11
1
and
 1
11

class Solution(object):
    def numDistinctIslands(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        #runtime complexity: O(h*w) space complexity O(2+2*h*w)
        def normalize(island):
            island.sort()
            origin_x, origin_y= island[0][0], island[0][1] #origin
            for p in island:
                p[0] -= origin_x
                p[1] -= origin_y
            return island
            #return [(p[0]-origin_x, p[1]-origin_y) for p in island]
        
        def dfs(i, j):
            if 0<=i<h and 0<=j<w and grid[i][j]==1: 
                island.append([i, j])
                grid[i][j]=False
                dfs(i+1,j)
                dfs(i-1,j)
                dfs(i,j+1)
                dfs(i,j-1)
                return True
                
        if not len(grid):   return 0
        h, w= len(grid), len(grid[0])
        
        ans=[]
        for i in range(h):   
            for j in range(w):
                island=[]
                if dfs(i, j):
                    norm= normalize(island)
                    if norm not in ans:    ans.append(norm)
    
        return len(ans)
        #---------------------------------------------
        move = zip((0, 0, -1, 1),(-1, 1, 0, 0))
        def dfs(x, y):
            level= [(x, y)]
            ans = []
            while level:
                x, y= level.pop(0)
                ans.append((x,y))
                if grid[x][y]:
                    grid[x][y] = 0
                    for dx, dy in move:
                        nx, ny = x+dx, y+dy
                        if 0<=nx<h and 0<=ny<w and grid[nx][ny]==1: level.append((nx, ny))
            
            top, left = min(x for x, y in ans), min(y for x, y in ans)
            return tuple( (x-top)*h + y-left for x, y in sorted(ans) )
            
        h, w= len(grid), len(grid[0])
        islands = set()
        for i in range(h):   
            for j in range(w):
                if grid[i][j]:    islands.add( dfs(i,j) )
        return len(islands)

#-----------------------------------------------------------------------------------------------------------------
695. Max Area of Island
https://leetcode.com/problems/max-area-of-island/description/
Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally
#-------------------------------------------------------------------------------------------------------------
827. Making A Large Island
https://leetcode.com/problems/making-a-large-island/description/
In a 2D grid of 0s and 1s, we change at most one 0 to a 1.
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).
Example 1:
Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
#------------------------------------------------------------------------------
463. Island Perimeter
https://leetcode.com/problems/island-perimeter/description/
Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]
Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:        
solution: 4-2*edege for each cell
                
                

partSplit.py

93. Restore IP Addresses
https://leetcode.com/problems/restore-ip-addresses/description/
#runtime complexity: O(n!) n=len(s)   
class Solution(object):
  def restoreIpAddresses(self, s):
      """
      :type s: str
      :rtype: List[str]
      """
      def dfs(s, substr, cnt):
          if not s and cnt==4:
              ans.append(substr)

          if s and cnt<=4:
              for i in range(len(s)):
                  part= s[:i+1]
                  if int(part) > 255 or (len(part)>1 and part[0]=='0'): return # 256/00/01/001/000
                  dfs(s[i+1:], substr+'.'+part if substr else part, cnt+1)

      ans= []
      dfs(s, '', 0)
      return ans
    
#-----------------------------------------------------------------------------------------
306. Additive Number / 842. Split Array into Fibonacci Sequence
https://leetcode.com/problems/additive-number/description/
Input: "112358"
Output: true 
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
      
#runtime complexity: O(n!) n=len(s)   space complexity: 
class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        def dfs(num, sublist):
            if len(sublist)>=3:
                if sublist[-1]!= sublist[-2]+sublist[-3]: return
                if not num: self.ans= True
            
            if num:
                for i in range(len(num)):
                    sub= num[:i+1]
                    if len(sub)>1 and sub[0]=='0': return 
                    dfs( num[i+1:], sublist+[int(sub)] )
                    
        self.ans=False
        dfs(num, [])
        return self.ans
  
140. Word Break II
https://leetcode.com/problems/word-break-ii/description/
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        #------------------------dp---------------------------
        N= len(s)
        dp = [False for i in range(N+1)]
        dp[0] = True
        for i in range(1, N+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:    dp[i] = True
        if not dp[N]: return [] 
        #-------------------------dfs-------------------     
        def dfs(i, substr):
            if i<N:
                for j in range(i+1, N+1):
                    if dp[j] and (s[i:j] in wordDict):
                        dfs(j, substr+' '+s[i:j]  if substr else s[i:j])
            else: ans.append(substr)
        ans= []
        dfs(0, '')
        return ans

291. Word Pattern II
https://leetcode.com/problems/word-pattern-ii/
Example 1:
Input: pattern = "abab", str = "redblueredblue"
Output: true
class Solution(object):
    def wordPatternMatch(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        def dfs(pattern, str, d1, d2):
            if not pattern and not str: return True
            
            if pattern:
                for i in range(len(str)):
                    p= pattern[0]
                    s= str[:i+1]
                    if p not in d1 and s not in d2:
                        d1[p]= s
                        d2[s]= p
                        if dfs(pattern[1:], str[i+1:],  d1, d2): return True  
                        del d1[p]
                        del d2[s]
                        
                    if (p in d1 and d1[p]==s) and (s in d2 and d2[s]==p):
                        if dfs(pattern[1:], str[i+1:], d1, d2): return True 
            return False

        d1= {}
        d2= {}
        return dfs(pattern, str, d1, d2)
  
  
  
  
  
  

two_option.py

320. Generalized Abbreviation
https://leetcode.com/problems/generalized-abbreviation/description/
Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

class Solution(object):
  def generateAbbreviations(self, word):
      """
      :type word: str
      :rtype: List[str]
      """
      """
      0000 word
      0001 wor1
      0010 wo1d
      0011 wo2
      0100 w1rd
      0101 w1r1
      0110 w2d
      0111 w3
      1000 1ord
      1001 1or1
      1010 1o1d
      1011 1o2
      1100 2rd
      1101 2r1
      1110 3d
      1111 4
      """
      #runtime complexity: O(2**n) n=len(word) space complexity O(1+n!)

        def updateStr(s):
            ans= ''
            cnt= 0
            while s:
                if s[0]=='1':
                    cnt+= 1
                    if len(s)==1 or s[1]!='1':  ans+= str(cnt)
                else:ans += s[0];cnt=0
                s= s[1:]
            return ans
        
        def dfs(word, substr):
            if not word:  ans.append( updateStr(substr) )
                
            if word:
                dfs( word[1:], substr+word[0] )
                dfs( word[1:], substr+'1')
        
        ans=[]
        dfs(word, '')
        return ans
#--------------------------------------------------------------------------------------------------------------------    
411. Minimum Unique Word Abbreviation
https://leetcode.com/problems/minimum-unique-word-abbreviation/description/
A string such as "word" contains the following abbreviations:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
Given a target string and a set of strings in a dictionary, find an abbreviation of this target string with the smallest possible length such that it does not conflict with abbreviations of the strings in the dictionary.
Each number or letter in the abbreviation is considered length = 1. For example, the abbreviation "a32bc" has length = 4.
Note:
In the case of multiple answers as shown in the second example below, you may return any one of them.
Assume length of target string = m, and dictionary size = n. You may assume that m ≤ 21, n ≤ 1000, and log2(n) + m ≤ 20.
Examples:
"apple", ["blade"] -> "a4" (because "5" or "4e" conflicts with "blade")
"apple", ["plain", "amber", "blade"] -> "1p3" (other valid answers include "ap3", "a3e", "2p2", "3le", "3l1").  
  

22. Generate Parentheses
https://leetcode.com/problems/generate-parentheses/description/
  
 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
] 
  
	public void dfs(List<String> list, String str, int open, int close, int max  ) {
		
		if(open==max && close==max) list.add(str);
		
		if( open < max ) dfs(list, str+"(" , open+1, close, max);
		if( close< open ) dfs(list, str+")" , open, close+1, max);
	}      
    
    public List<String> generateParenthesis(int n) {
		List<String> list= new ArrayList<>();
		
		dfs(list, "", 0, 0, n);
		
		System.out.println(list);
		return list;
	} 

union find.py

305. Number of Islands II
https://leetcode.com/problems/number-of-islands-ii/

lass Solution(object):
    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        #https://leetcode.com/problems/number-of-islands-ii/discuss/75459/JavaPython-clear-solution-with-UnionFind-Class-(Weighting-and-Path-compression)
        
        #time 
        ans = []
        islands = Union()
        for p in map(tuple, positions):
            islands.add(p)
            for dp in (0, 1), (0, -1), (1, 0), (-1, 0):
                q = (p[0] + dp[0], p[1] + dp[1])
                if q in islands.id:
                    islands.unite(p, q)
            ans += [islands.count]
        return ans

    
class Union(object):
    def __init__(self):
        self.id = {}
        self.sz = {}
        self.count = 0

    def add(self, p):
        self.id[p] = p
        self.sz[p] = 1 #size
        self.count += 1
    
    #find compoent element belongs to find the root of that component by the following the parent nodes 
    #until a self loop is reached(a node who's parent is self)
    def root(self, i):
        if i != self.id[i]:
            self.id[i]= self.root( self.id[i] )
        return self.id[i]
        """
        while i != self.id[i]:
            self.id[i] = self.id[self.id[i]]
            i = self.id[i]
        return i        
        """

    def unite(self, p, q):
        i, j = self.root(p), self.root(q)
        if i == j:    return
        
        # i,j different, make one of root node as the parent of other
        #make sure always i < j 
        #if self.sz[i] > self.sz[j]: i, j = j, i
        
        self.id[i] = j
        self.sz[j] += self.sz[i]
        self.count -= 1
        
  737. Sentence Similarity II
  https://leetcode.com/problems/sentence-similarity-ii/
  
  684. Redundant Connection
  https://leetcode.com/problems/redundant-connection/  
  
  547. Friend Circles
  https://leetcode.com/problems/friend-circles/
    
    

win game.py

294. Flip Game II
https://leetcode.com/problems/flip-game-ii/description/
  
class Solution(object):
    def canWin(self, s):
        """
        :type s: str
        :rtype: bool
        """
        #runtime complexity O(n)  space compexity O(n)
        for i in range(len(s) - 1): 
            if s[i:i+2] == "++": 
                if not self.canWin(s[:i] + "--" + s[i+2:] ):    return True
        return False
      
      
 

word_search.py

2D: 79  Word Search
  
37. Sudoku Solver 
Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.
  
class Solution {
    public boolean isValid(char[][] board, int row, int col, char c){
        for(int i=0; i<9; i++){
            if( board[row][i]== c) return false;
            if( board[i][col]== c) return false;
            if( board[ 3*(row/3)+ i/3 ][ 3*(col/3) + i%3 ]== c) return false; 
        }
        return true;
    }
    
    public boolean dfs(char[][] board){
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if( board[i][j]=='.'){
                    for(char c='1'; c<='9'; c++){
                        if(isValid(board, i, j, c)){
                            
                            board[i][j]= c;
                            if( dfs(board) ) return true;
                            else board[i][j]= '.';
                        }
                    }
                    return false;
                }
            }    
        }
        return true;
    }
    
    //O( 9!^9)
    public void solveSudoku(char[][] board) {
        dfs(board);
    }
}

51. N-Queens
https://leetcode.com/problems/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.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

class Solution {
    List<List<String>> ans= new ArrayList<List<String>>();
    
	Set<Integer> cols= new HashSet<>();
	Set<Integer> diagonal1= new HashSet<>();
	Set<Integer> diagonal2= new HashSet<>();
    int[][] board;

    public List<String> toList(int N){
        List<String> list= new ArrayList<>();
        for(int i=0; i<N; i++){
            String str="";
            for(int j=0; j<N; j++){
                if(board[i][j]==0) str += ".";
                else str +="Q";
            }
            list.add(str);
        }
        return list;
    }
    
    
	public void dfs(int row, int N) {
		for(int col=0; col<N; col++) {
			if(row==N) {
                ans.add( toList(N) );
				return;
			}
			
			int diag1= row-col, diag2= row+col;
			if ( cols.contains(col) || diagonal1.contains(diag1) || diagonal2.contains(diag2) ) continue;

			cols.add(col);
			diagonal1.add(diag1);
			diagonal2.add(diag2);
			board[row][col]= 1;

			dfs(row+1, N);
			
			cols.remove(col);
			diagonal1.remove(diag1);
			diagonal2.remove(diag2);
			board[row][col]= 0;
		}
	}    
    
    public List<List<String>> solveNQueens(int n) {
       	board= new int[n][n];
		dfs(0, n); 
        return ans;
    }
}


79. Word Search
https://leetcode.com/problems/word-search/description/

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        #runtime complexity: O(n*n) n=h*w space comlexity: O(2)
        def dfs(i, j, word):
            if self.ans: return 
            
            if not word:    
                self.ans= True
                return
            
            if 0<=i<h and 0<=j<w and board[i][j]==word[0]:
                tmp= board[i][j]
                board[i][j]= False
                dfs(i+1, j, word[1:])
                dfs(i-1, j,word[1:])
                dfs(i, j+1,word[1:])
                dfs(i, j-1,word[1:])
                board[i][j]= tmp
                
        if not board:   return False 
        
        self.ans= False
        h, w= len(board), len(board[0])
        for i in range(h):
            for j in range(w):
                dfs(i,j,word)
        return self.ans
      
#-----------------------------------------------------------------------------    
212. Word Search II
find all words in the board.

Input: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Output: ["eat","oath"]

  37. Sudoku Solver
  https://leetcode.com/problems/sudoku-solver/description/
    
  class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        def isValid(x,y):
            tmp=board[x][y]; board[x][y]= False
            for i in range(9):
                if board[i][y]==tmp: return False
            for i in range(9):
                if board[x][i]==tmp: return False
            for i in range(3):
                for j in range(3):
                    if board[(x/3)*3+i][(y/3)*3+j]==tmp: return False
            board[x][y]=tmp
            return True
        
        def dfs():
            for i in range(9):
                for j in range(9):
                    if board[i][j]=='.':
                        for k in '123456789':
                            board[i][j]=k
                            if isValid(i,j) and dfs(): return True
                            board[i][j]='.'
                        return False
            return True
        dfs()