backtracking 总结

backtracking 不同题目不完全汇总

### Subsets
        def backtrack(list, templist,nums,start):
            list.append(templist[:])
            for i in range(start,len(nums)):
                templist.append(nums[i])
                backtrack(list,templist,nums,i+1)
                templist.pop()      

        list=[]
        nums.sort()
        backtrack(list,[],nums,0)
        return list
### Subsets II
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtrack(list, templist,nums,start):
            list.append(templist[:])
            for i in range(start,len(nums)):
                if i > start and nums[i] == nums[i-1]: continue
                templist.append(nums[i])
                backtrack(list,templist,nums,i+1)
                templist.pop()      

        list=[]
        nums.sort()
        backtrack(list,[],nums,0)
        return list
### Permutations
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(list, templist,nums):
            
            if len(templist)==len(nums): list.append(templist[:])
            else:
                for i in range(0,len(nums)):
                    if nums[i] in templist: continue
                    templist.append(nums[i])
                    backtrack(list,templist,nums)
                    templist.pop()      

        list=[]
        #nums.sort()
        backtrack(list,[],nums)
        return list
### Permutations II
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
             
        def backtrack(list, templist,nums,used):
            
            if len(templist)==len(nums): list.append(templist[:])
            else:
                for i in range(0,len(nums)):
                    if used[i] or (i > 0 and nums[i] == nums[i-1] and (not used[i - 1])): continue
                    used[i]=True
                    templist.append(nums[i])
                    backtrack(list,templist,nums,used)
                    used[i] = False 
                    templist.pop()      

        list=[]
        used=[False]*len(nums)
        nums.sort()
        backtrack(list,[],nums,used)
        return list
### combination sum
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        def backtrack(list, templist,nums,remain,start):
            
            if remain < 0: return
            elif remain == 0: list.append(templist[:])
            else:
                for i in range(start,len(nums)):
                    
                    templist.append(nums[i])
                    backtrack(list,templist,nums,remain - nums[i], i)
                    templist.pop()      
        nums=candidates
        list=[]
        nums.sort()
        backtrack(list,[],nums,target,0)
        return list
### combination sum II
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
             
        def backtrack(list, templist,nums,remain,start):
            
            if remain < 0: return
            elif remain == 0: list.append(templist[:])
            else:
                for i in range(start,len(nums)):
                    if (i > start) and (nums[i] == nums[i-1]): continue
                    templist.append(nums[i])
                    backtrack(list,templist,nums,remain - nums[i], i+1)
                    templist.pop()      
        nums=candidates
        list=[]
        nums.sort()
        backtrack(list,[],nums,target,0)
        return list
### Palindrome Partitional 
    def partition(self, s: str) -> List[List[str]]:
        
        def backtrack(list, templist,s,start):
            
            if start==len(s): list.append(templist[:])  
            else:
                for i in range(start,len(s)):
                    if s[start:i+1]==s[start:i+1][::-1]:
                        templist.append(s[start:i+1])
                        backtrack(list,templist,s, i+1)
                        templist.pop()      

        list=[]
        backtrack(list,[],s,0)
        return list