Backtracking

1 Letter Combinations of a Phone Number

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "":
            return []
        dic =  {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = ['']
        for d in digits:
            new_res = []
            res = [ s + c for s in res for c in dic[d] ]
        return res

2 Subsets

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        return self.helper(nums, [], [])

    def helper(self, nums, path, res):
        if not nums:
            res.append(path)
            return

        self.helper(nums[1:], path+[nums[0]], res)
        self.helper(nums[1:], path, res)
        return res

3 Permutations

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        return self.hepler(nums, [], [])

    def hepler(self, nums, path, res):
        if not nums:
            res.append(path)
            return

        for i in range(len(nums)):
            self.hepler(nums[:i]+nums[i+1:], path+[nums[i]], res)
        return res

4 Permutations II

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        return self.hepler(sorted(nums), [], [])

    def hepler(self, nums, path, res):
        if not nums:
            res.append(path)
            return

        for i in range(len(nums)):
            if i>0 and nums[i]==nums[i-1]:
                continue
            self.hepler(nums[:i]+nums[i+1:], path+[nums[i]], res)
        return res

5 Remove Invalid Parentheses

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        queue = [s]
        ans = []
        found = False
        visited = set()
        while queue:
            l = len(queue)
            for i in range(l):
                tmp = queue.pop(0)

                if self.isValid(tmp):
                    ans.append(tmp)
                    found = True

                if not found:
                    for i in range(len(tmp)):
                        if tmp[i] in ['(', ')']:
                            candidate = tmp[:i] + tmp[i+1:]
                            if candidate not in visited:
                                queue.append(candidate)
                                visited.add(candidate)
            if found:
                break
        return ans

    def isValid(self, s):
        cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
            if c == ')':
                cnt -= 1
            if cnt < 0:
                return False
        return cnt == 0