代码随想录算法训练营第27天 | 回溯3：93.复原IP地址、78.子集、90.子集II

93.复原IP地址
https://leetcode.cn/problems/restore-ip-addresses/submissions/547344868/
代码随想录
https://programmercarl.com/0093.复原IP地址.html#算法公开课
78.子集
https://leetcode.cn/problems/subsets/description/
代码随想录
https://programmercarl.com/0078.子集.html
90.子集II
https://leetcode.cn/problems/subsets-ii/description/
代码随想录
https://programmercarl.com/0090.子集II.html

93.复原IP地址

题解思路

• 和切割回文字符串一样
• 判断条件有区别
• 考虑是否为单纯为0

题解代码

class Solution:
    def __init__(self):
        self.path = []
        self.res = []
    def back_trace(self,s,index):
        if len(self.path)==4 and index==len(s):
            self.res.append(".".join(self.path[:]))
            return
        if len(self.path)>4:
            return
        for i in range(index,len(s)):
            if self.panduan(s[index:i+1]):
                ## 往后取一位
                self.path.append(s[index:i+1])
                self.back_trace(s,i+1)
                self.path.pop()
    def panduan(self,s):
        if len(s)>1 and s[0]=="0":
            ##单独一个0是特殊情况
            return False
        try:
            data = int(s)
            if 0<=data<=255:
                return True
            else:
                return False
        except:
            return False
    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s)==0:
            return self.res
        self.back_trace(s,0)
        return self.res

78.子集

题解思路

• 数组子集：遍历所有可能节点

题解代码

class Solution:
    def __init__(self):
        self.res = []
        self.path = []
    def back_trace(self,nums,index,used):
        self.res.append(self.path[:])
        if index==len(nums):
            return

        for i in range(index,len(nums)):
            self.path.append(nums[i])
            self.back_trace(nums,i+1,used)
            self.path.pop()


    def subsets(self, nums: List[int]) -> List[List[int]]:
        if len(nums)==0:
            return [[]]
        self.back_trace(nums,0,[0]*len(nums))
        return self.res

90.子集II

题解思路

• 和前面思路重复：单个元素不能重复利用；但是可以出现重复元素

class Solution:
    def __init__(self):
        self.res = []
        self.path = []
    def back_trace(self,nums,index,used):
        self.res.append(self.path[:])
        if index==len(nums):
            return

        for i in range(index,len(nums)):
            if i>0 and nums[i]==nums[i-1] and used[i-1]==0:
                continue
            ##去掉重复元素
            used[i]=1
            self.path.append(nums[i])
            self.back_trace(nums,i+1,used)
            ## 不重复使用元素
            self.path.pop()
            used[i]=0

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        if len(nums)==0:
            return [[]]
        nums = sorted(nums)
        self.back_trace(nums,0,[0]*len(nums))
        return self.res
``