<h1>
Backtracking
</h1>

<h2>
- [Ｏ] 401. Binary Watch
</h2>

<h3>
題目
</h3>

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

For example, the below binary watch reads "4:51".


Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.

The hour must not contain a leading zero.

For example, "01:00" is not valid. It should be "1:00".
The minute must be consist of two digits and may contain a leading zero.

For example, "10:2" is not valid. It should be "10:02".

**Example1**

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

<h3>
思路
</h3>

利用Backtracking慢慢找，把turnedOn的數字分成時和分，再慢慢做recurssion。

class Solution(object):
    def __init__(self):
        self.ans=[]
        
    def readBinaryWatch(self, turnedOn):
        hour=[1,2,4,8]
        minute=[1,2,4,8,16,32]
        if turnedOn==0:
            return ["0:00"]
        for i in xrange(0,5):
            if turnedOn<i:
                break
            self.combineTime(hour,minute,0,0,i,turnedOn-i)
        return self.ans
        
    def combineTime(self,hourTable,minuteTable,hour,minute,turnedOnhour,turnedOnminute):
        if hour>11 or minute>59:
            return 
        if turnedOnhour==0 and turnedOnminute==0:
            if minute<10:
                if self.ans.count(str(hour)+":"+"0"+str(minute))>0:
                    return
                self.ans.append(str(hour)+":"+"0"+str(minute))
            else:
                if self.ans.count(str(hour)+":"+str(minute))>0:
                    return
                self.ans.append(str(hour)+":"+str(minute))
        else:
            for i in xrange(0,len(hourTable)):
                if turnedOnhour==0:
                    break
                if hour>=hourTable[i]:
                    continue
                hour+=hourTable[i]
                turnedOnhour-=1
                self.combineTime(hourTable,minuteTable,hour,minute,turnedOnhour,turnedOnminute)
                turnedOnhour+=1
                hour-=hourTable[i]
            for i in xrange(0,len(minuteTable)):
                if turnedOnminute==0:
                    break
                if minute>=minuteTable[i]:
                    continue
                minute+=minuteTable[i]
                turnedOnminute-=1
                self.combineTime(hourTable,minuteTable,hour,minute,turnedOnhour,turnedOnminute)
                turnedOnminute+=1
                minute-=minuteTable[i]
            
                
        """
        :type turnedOn: int
        :rtype: List[str]
        """
        

---

<h2>
- [O]1980. Find Unique Binary String
</h2>

<h3>
題目
</h3>

Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.

**Example 1**

Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.

<h3>
思路
</h3>

利用Backtracking依序排列每種可能的Binary String，若發現題目沒有的就return。

class Solution(object):
    def makenumbers(self,table,size,target):
        if len(target)==size:
            if table.get(target)==None:
                return target
            else:
                return -1
        
        zero=target+"0"
        one=target+"1"
        zeroResult=self.makenumbers(table,size,zero)    
        oneResult=self.makenumbers(table,size,one)
        if zeroResult!=-1:
            return zeroResult
        else:
            return oneResult
        
    def findDifferentBinaryString(self, nums):
        table={}
        for i in xrange(0,len(nums)):
            table[nums[i]]=0
        zero=self.makenumbers(table,len(nums[0]),"0")
        one= self.makenumbers(table,len(nums[0]),"1")
        if zero!=-1:
            return zero
        return one
    
        
        """
        :type nums: List[str]
        :rtype: str
        """

---

<h2>
- [O]797. All Paths From Source to Target
</h2>

<h3>
題目
</h3>

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

**Example1**


Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

<h3>
思路
</h3>

利用Backtracking從node 0一路追蹤到底。

class Solution(object):
    def __init__(self):
        self.ans=[]
        
    def allPathsSourceTarget(self, graph):
        self.traversal(graph,[0])
        return self.ans
    
    def traversal(self,graph,target):
        index=target[-1]
        if len(graph[index])==0 or target[-1]==len(graph)-1:
            if target[-1]==len(graph)-1:
                sample=copy.deepcopy(target)
                self.ans.append(sample)
        else:
            for i in xrange(0,len(graph[index])):
                target.append(graph[index][i])
                self.traversal(graph,target)
                target.pop()
              
                    
        """
        :type graph: List[List[int]]
        :rtype: List[List[int]]
        """
        

---

<h2>
- [O]131.Palindrome Partitioning
</h2>

<h3>
題目
</h3>

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

**Example1**

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

<h3>
思路
</h3>

從頭開始一個一個慢慢加，如果符合 Palindrome就去跑Backtracking。

class Solution(object):
    def __init__(self):
        self.ans=[]
    def partition(self, s):
        self.palidromeProcess([],s)
        return self.ans
    def palidromeProcess(self,table,left):

        if len(left)==0:
            palidromeAns=copy.deepcopy(table)
            self.ans.append(palidromeAns)
            return
        for i in range(0,len(left)):
            start=0
            end=i
            flag=0
            while start<end:
                if left[start]==left[end]:
                    start+=1
                    end-=1
                else:
                    flag=-1
                    break
            if flag==0:
                table.append(left[0:i+1])
                self.palidromeProcess(table,left[i+1:])
                table.pop()
                
        """
        :type s: str
        :rtype: List[List[str]]
        """

---

<h2>
- [X]980. Unique Paths III
</h2>

<h3>
題目
</h3>

You are given an m x n integer array grid where grid[i][j] could be:

1 representing the starting square. There is exactly one starting square.
2 representing the ending square. There is exactly one ending square.
0 representing empty squares we can walk over.
-1 representing obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

**Example1**


Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

<h3>
Discussion
</h3>

利用DFS去搜尋所有可能性。

class Solution(object):
    def uniquePathsIII(self, A):
        self.res = 0
        m, n, empty = len(A), len(A[0]), 1
        for i in range(m):
            for j in range(n):
                if A[i][j] == 1:
                    x, y = (i, j)
                elif A[i][j] == 0:
                    empty += 1

        def dfs(x, y, empty):
            if not (0 <= x < m and 0 <= y < n and A[x][y] >= 0): return
            if A[x][y] == 2:
                self.res += empty == 0
                return
            A[x][y] = -2
            dfs(x + 1, y, empty - 1)
            dfs(x - 1, y, empty - 1)
            dfs(x, y + 1, empty - 1)
            dfs(x, y - 1, empty - 1)
            A[x][y] = 0
        dfs(x, y, empty)
        return self.res
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        

---

<h2>
- [O]1255. Maximum Score Words Formed by Letters
</h2>

<h3>
題目
</h3>

Given a list of words, list of single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given by score[0], score[1], ... , score[25] respectively.

**Example1**

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation:
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.

<h3>
思路
</h3>

去枚舉所有可能性，找出最大值。

class Solution(object):
    def __init__(self):
        self.ans=0
        
    def maxScoreWords(self, words, letters, score):
        table={}
        for character in letters:
            if table.get(character)==None:
                table[character]=1
            else:
                table[character]+=1
        for i in xrange(0,len(words)):
            scoreNow=0
            flag=0
            copyTable=copy.deepcopy(table)
            for character in words[i]:
                scoreNow+=score[ord(character)-ord("a")]
                if copyTable.get(character)==None:
                    scoreNow=0
                    flag=-1
                    break
                else:
                    if copyTable[character]==0:
                        scoreNow=0
                        flag=-1
                        break
                    copyTable[character]-=1
            if flag==0:
                self.ans=max(self.ans,scoreNow)
                self.checkScore(copyTable,i+1,scoreNow,score,words)
        return self.ans
           
                
                
                
                
    def checkScore(self,table,startPos,score,scoreTable,words):
        if startPos>=len(words):
            return 
        for i in xrange(startPos,len(words)):
            scoreNow=score
            flag=0
            copyTable=copy.deepcopy(table)
            for character in words[i]:
                scoreNow+=scoreTable[ord(character)-ord("a")]
                if copyTable.get(character)==None:
                    scoreNow=score
                    flag=-1
                    break
                else:
                    if copyTable[character]==0:
                        scoreNow=score
                        flag=-1
                        break
                    copyTable[character]-=1
            if flag==0:
                self.ans=max(self.ans,scoreNow)
                self.checkScore(copyTable,i+1,scoreNow,scoreTable,words)
        
      
        
                
        """
        :type words: List[str]
        :type letters: List[str]
        :type score: List[int]
        :rtype: int
        """