【leetcode刷刷】93.复原IP地址 、78.子集 、90.子集II

93.复原IP地址

1. 跟之前的分割序列很像，所以也比较好想

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # 找3个分割点？
        # 最后一个分割点的时候，判断path，加入res
        # 不符合规则的就跳过
        self.res = []
        self.backtracking(s, 0, [])
        return self.res

    def backtracking(self, s, start_index, path):
        if len(path) == 4 and start_index == len(s):
            self.res.append(".".join(path))
            return
        if len(path) > 4: return 


        for i in range(start_index, len(s)):
            if i - start_index > 2: continue
            if self.is_valid(s[start_index:i+1]):
                path.append(s[start_index:i+1])
                self.backtracking(s, i+1, path)
                path.pop()

    def is_valid(self, s):
        if s[0] == '0' and len(s) > 1:
            return False
        if int(s) > 255: return False
        return True

78.子集

1. 和组合的思路是一样的，而且应该不能剪枝吧
2. self.res.append(path[:])在回溯上面，可以使得[]也在答案里面

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # 所有的子集，不能包含重复子集
        # 元素互不相同，所以子集不会重复    
        # 和组合问题的区别是什么？？？？
        self.res = [[]]
        self.backtracking(nums, 0, [])
        return self.res

    def backtracking(self, nums, start_index, path):
	    self.res.append(path[:])
        for i in range(start_index, len(nums)):
            path.append(nums[i])

            self.backtracking(nums, i+1, path)
            path.pop()

90.子集II

1. 这个去重，和组合的去重是一样的。要注意一定要先排序。刚写的时候忘记了。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        nums.sort()
        self.backtracking(nums, 0, [])
        return self.res

    def backtracking(self, nums, start_index, path):
        self.res.append(path[:])

        for i in range(start_index, len(nums)):
            if i > start_index and nums[i] == nums[i-1]:
                continue
            path.append(nums[i])
            self.backtracking(nums, i+1, path)
            path.pop()