复原IP地址

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：”0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1“ 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

class Solution:
    def isok(self,s,s_index,e_index):
        if s_index > e_index:
            return False
        if s[s_index] == '0' and s_index != e_index:
            return False
        if int(s[s_index:e_index+1]) > 255:
            return False
        return True
    def backtracking(self,s,index,count,cur,result):
        if count == 3 and self.isok(s,index,len(s)-1):
            cur += s[index:]
            result.append(cur)
        for i in range(index,len(s)):
            if self.isok(s,index,i):
                temp = s[index:i+1]
                count += 1
                self.backtracking(s,i+1,count,cur+temp+'.',result) #隐式回溯，cur本身不变
                count -=1

    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        self.backtracking(s,0,0,'',result)
        return result

不能直接用s，字符串不可变还是要设置个变量接住

子集

78. 子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

class Solution:
    def backtracking(self,nums,index,path,result):
        for i in range(index,len(nums)):
            path.append(nums[i])
            result.append(path[:])
            self.backtracking(nums,i+1,path,result)
            path.pop()

    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = [[]]
        self.backtracking(nums,0,[],result)
        return result

真别说，连剪枝都不要，但是这道题每个节点都要记录一下

子集II

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

class Solution:
    def backtracking(self,nums,index,path,result,used):
        for i in range(index,len(nums)):
            if i>index and nums[i]==nums[i-1] and not used[i-1]:
                continue 
            path.append(nums[i])
            used[i] = True
            result.append(path[:])
            self.backtracking(nums,i+1,path,result,used)
            path.pop()
            used[i] = False

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        result = [[]]
        nums.sort()
        used = [False]*len(nums)
        self.backtracking(nums,0,[],result,used)
        return result