Day 28 回溯：93. 复原IP, 78|90. 子集 I II, 698. 划分为k个相等的子集

93. 复原 IP 地址

思路
- example
- 返回所有可能的有效 IP 地址: 回溯
- 切割：[左边界，右边界] + '.'
  - 桶装球（4个桶）
  - 左边界: "给定"
    - 如果左边界=0，则右边界也是0。
  - 右边界: 切割点，模向搜索
  - 桶限制：
    - 4个 (深度）
    - 每个size <= 3
    - 数字 <= 255
复杂度. 时间：O(), 空间: O()

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(s, start):
            if start == len(s) and len(path) == 4:
                res.append('.'.join(path))
            for i in range(start, len(s)):
                if int(s[start:i+1]) <= 255:
                    path.append(s[start:i+1])
                    backtrack(s, i+1)
                    path.pop()
                if s[start] == '0':
                    break             
        res, path = [], []
        backtrack(s, 0)
        return res

加上一点剪枝

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(s, start, depth):
            if depth == 3 and len(s)-start > 3:
                return 
            if depth == 4 and start == len(s):
                res.append('.'.join(path))
                return 
            for i in range(start, min(start+3, len(s))):
                if int(s[start:i+1]) <= 255:
                    path.append(s[start:i+1])
                    backtrack(s, i+1, depth+1)
                    path.pop()
                if s[start] == '0':
                    break 
        if len(s) < 4 or len(s) > 12:
            return []
        res, path = [], []
        backtrack(s, 0, 0)
        return res

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(start):
            if start == n and len(path) == 4:
                res.append('.'.join(path))
                return 
            if len(path) == 4 and start < n:
                return 
            for i in range(start, min(n, start+3)):
                if s[start] == '0' and i > start:
                    break 
                num = int(s[start:i+1])
                if num >= 0 and num <= 255:
                    path.append(s[start:i+1])
                    backtrack(i+1)
                    path.pop()
        res, path = [], []
        n = len(s)
        backtrack(0) 
        return res

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(start_idx):
            if start_idx == len(s):
                if len(path) == 4:
                    res.append('.'.join(path)) 
                return  
            for i in range(start_idx, min(start_idx+3, len(s))):
                if s[start_idx] == '0' and i > start_idx: # !!!
                    break   
                if int(s[start_idx:i+1]) <= 255:
                    if len(path) == 4:
                        break  
                    path.append(s[start_idx:i+1])
                    backtrack(i+1)
                    path.pop()  
        res, path = [], []
        backtrack(0) 
        return res

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(start):
            if start == n:
                if len(path) == 4:
                    res.append('.'.join(path))
                return 
            if len(path) >= 4:
                return 
            for i in range(start, min(start + 3, n)):
                if int(s[start:i+1]) <= 255:
                    path.append(s[start:i+1])
                    backtrack(i+1)
                    path.pop()
                if s[start] == '0': # !!!
                    break 
        n = len(s) 
        res, path = [], []
        backtrack(0)
        return res

78. 子集

思路
- example
- 数组中的元素互不相同
- 返回该数组所有可能的子集: 回溯
- [1,2] 和 [2,1]是重复的，只取一种。
- 桶装球
  - 球（数字）不能重复取
- 注意return 条件

if start == len(nums):
   return

复杂度. 时间：O(), 空间: O()

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums, start):
            res.append(path[:])
            if start == len(nums):
                return 
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(nums, i+1)
                path.pop()
        res, path = [], []
        backtrack(nums, 0)
        return res

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start):
            if start <= n:
                res.append(path[:])
                # return # !!! 
            for i in range(start, n):
                path.append(nums[i]) 
                backtrack(i+1)
                path.pop()
        res, path = [], []
        n = len(nums)
        backtrack(0)
        return res

90. 子集 II

思路
- example
- 数组可能包含重复元素
- 返回该数组所有可能的子集: 回溯
- 去重 (同层）
  - sort
  - startIndex
复杂度. 时间：O(), 空间: O()

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums, start):
            res.append(path[:])
            if start == len(nums):
                return 
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i-1]: # 同层去重
                    continue  
                path.append(nums[i])
                backtrack(nums, i+1)
                path.pop()
        res, path = [], []
        nums.sort() # 排序，方便去重
        backtrack(nums, 0)
        return res

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start):
            if start <= n:
                res.append(path[:])
            for i in range(start, n):
                if i > start and nums[i] == nums[i-1]:
                    continue 
                path.append(nums[i])
                backtrack(i+1)
                path.pop()
        nums.sort()
        n = len(nums)
        res, path = [], []
        backtrack(0)
        return res

698. 划分为k个相等的子集

思路
- example
- 参考: 416. 分割等和子集

0-1背包（每个数字使用一次）
dp[i][j]: 数字nums[0],...,nums[i]中选取若干个，背包容量为j所能容纳的最大价值（子集和）。
Goal: dp[-1][target] where target = sum(nums)//2 (assuming the sum is even)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_ = sum(nums)
        if sum_ % 2 == 1: return False
        target = sum_ // 2
        dp = [[0] * (target+1) for _ in range(len(nums))]
        for j in range(nums[0], target+1):
            dp[0][j] = nums[0]
        for i in range(1, len(nums)):
            for j in range(target+1):
                if j < nums[i]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
        return dp[len(nums)-1][target] == target

k > 2时如何推广上面的DP方法？

思路

盒视角

球的视角分两种情况：
1、第一个球可以不装进任何一个盒子，这样的话你就需要将剩下 n - 1 个球放入 k 个盒子。
2、第一个球可以装进 k 个盒子中的任意一个，这样的话你就需要将剩下 n - 1 个球放入 k - 1 个盒子。

球盒模型
把装有 n 个数字的数组 nums 分成 k 个和相同的集合，你可以想象将 n 个数字分配到 k 个「桶」里，最后这 k 个「桶」里的数字之和要相同。

回溯：球视角（球放桶）
- 纵向：球n
- 横向：桶k
- time: $O(k^n)$

// 主函数
boolean canPartitionKSubsets(int[] nums, int k) {
    // 排除一些基本情况
    if (k > nums.length) return false;
    int sum = 0;
    for (int v : nums) sum += v;
    if (sum % k != 0) return false;

    // k 个桶（集合），记录每个桶装的数字之和
    int[] bucket = new int[k];
    // 理论上每个桶（集合）中数字的和
    int target = sum / k;
    // 穷举，看看 nums 是否能划分成 k 个和为 target 的子集
    return backtrack(nums, 0, bucket, target);
}

// 递归穷举 nums 中的每个数字
boolean backtrack(
    int[] nums, int index, int[] bucket, int target) {

    if (index == nums.length) {
        // 检查所有桶的数字之和是否都是 target
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] != target) {
                return false;
            }
        }
        // nums 成功平分成 k 个子集
        return true;
    }
    
    // 穷举 nums[index] 可能装入的桶
    for (int i = 0; i < bucket.length; i++) {
        // 剪枝，桶装装满了
        if (bucket[i] + nums[index] > target) {
            continue;
        }
        // 将 nums[index] 装入 bucket[i]
        bucket[i] += nums[index];
        // 递归穷举下一个数字的选择
        if (backtrack(nums, index + 1, bucket, target)) {
            return true;
        }
        // 撤销选择
        bucket[i] -= nums[index];
    }

    // nums[index] 装入哪个桶都不行
    return false;
}

桶视角（桶装球）
- 纵向：桶k
- 横向: 球n
- time: $O(k*2^n)$
- 「少量多次」

深搜桶，每一层有n个球供选择（有些球已选过要跳过）

状态（用bit)。第j个数已经被选：1<<j (把1的二进制左移j位）。比如（1001）表示第0，3个数已经被选过。总共2^n个壮态，（111…111）表示全部n个数都已进桶。
注意，假设状态为(1001),且第一桶还没填满，那么这个状态说明0，3号球在第一个桶；这个状态可以表示第一桶有球0，第二桶有球3？不可以，因为这样的话必须要先把第一个桶填满，状态不会是（1001）。

memo（额外数组存计算过的状态）, dp[state] = -1, 0, 1表示state 没有计算，不work，work三种情况。目标：dp[total], total = (1<<n)-1或者说2^n-1。返回dp[total] == 1即可。
倒推方法。最后的结果其实是反馈到最初的状态的。

排序，加快减枝。

bucket一个一个来填满（和为target).到最后每个数都用到时，就找到一个分组方式。因为前面有判断当和>target时会停止继续搜索，到最后只能<=target，其实<是不可能的，因为这样的话前面的bucket至少有一个的和会大于target,矛盾。另外不需要对bucket进行计数，因为target=Sum//k,每个bucket和为target,全都完成必然是用到了k个bucket.

# 超时
class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        def dfs(nums, state, curSum): # dfs， 纵向：桶， 当前桶所装球的总和为curSum，一个桶可能需要多个纵向搜索来完成。
            if dp[state] != -1: # memo 已计算过
                return dp[state]
            if state == total: # 全部球已放进桶, 根据剪枝条件，此时curSum必定=target
                dp[state] = 1
                return dp[state]
            for j in range(n): # 横向选择：球
                if state & (1<<j) == 1: continue # 第j个球已经使用过
                if curSum+nums[j] > target: break # 剪枝
                new_state = state | (1<<j) # 更新状态
                if dfs(nums, new_state, (curSum+nums[j]) % target) == 1: # 如果curSum+nums[j]=target,自动启用下一个桶。
                    dp[new_state] = 1 # 修改结果，方便迅速回到最初状态，结束程序。
                    return dp[new_state] # 提早结束搜索
            dp[state] = 0 # 失败，当前状态不管如何加别的球都不能完成任务。
            return dp[state]
        nums.sort() # 排序, 方便剪枝
        n = len(nums)
        Sum = sum(nums)
        if Sum % k != 0: return False
        target = Sum // k
        if nums[-1] > target: return False
        # 状态 e.g., (01010001)_2
        total = (1<<n) - 1 # 状态总数 2^n - 1
        dp = [-1] * (total+1) # 记忆化
        return dfs(nums, 0, 0)

# 超时
class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        def backtrack(k, bucketSum, nums, start):
            nonlocal used
            if k == 0: # 只剩下0个桶，成功
                return True 
            if used in memo: # 记忆化
                return memo[used]
            if bucketSum == target: # i当前桶装满
                res = backtrack(k-1, 0, nums, 0) # 下一个桶 
                memo[used] = res
                return res  
            for i in range(start, len(nums)):
                if used & (1 << i):
                    continue   
                if nums[i] + bucketSum > target:
                    continue   
                used = used | (1 << i)
                bucketSum += nums[i]  
                if backtrack(k, bucketSum, nums, i+1):
                    return True  # 提早返回结果
                used = used ^ (1 << i)  
                bucketSum -= nums[i]  
            return False  
        # 不需要预先排序
        sum_ = sum(nums)
        if sum_ % k != 0:
            return False  
        target = sum_ // k  
        used = 0 # 状态，bit
        memo = [-1 for _ in range(1<<len(nums))]
        return backtrack(k, 0, nums, 0)

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        # @cache
        cache = dict()      # 手动实现记忆化单元
        def dfs(state, summ):
            if (state, summ) in cache:      # 从记忆中直接读取
                return cache[(state, summ)]
            if state == (1<<n) - 1:         # 所有整数均已划分，结束递归，并返回True
                # cache[(state, summ)] = True
                return True
            for j in range(n):
                if summ + nums[j] > target: # nums已升序排列，当前数字不行，后续肯定也不行
                    break
                if state & (1<<j) == 0:             # nums[i]暂未被划分
                    next_state = state + (1<<j)     # 划分nums[j]
                    if dfs(next_state, (summ+nums[j]) % target):    # 划分nums[j]能形成有效方案
                        cache[(state, summ)] = True     # 加入记忆化单元【避免后续重复计算】
                        return True
            cache[(state, summ)] = False                # 加入记忆化单元【避免后续重复计算】
            return False
        total = sum(nums)
        if total % k != 0:
            return False
        n = len(nums)
        target = total // k     # 目标非空子集的和
        nums.sort()             # 升序排列
        if nums[-1] > target:   # 最大值超过目标子集和，无法划分
            return False
        return dfs(0, 0)

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        cache = dict()
        def dfs(state, cur_sum):
            if (state, cur_sum) in cache:
                return cache[(state, cur_sum)] 
            if state == (1<<len(nums))-1: 
                return True   
            for j in range(len(nums)):
                if state & (1<<j) == 0:
                    if cur_sum + nums[j] > target:
                        break  
                    if dfs(state+(1<<j), (cur_sum+nums[j]) % target):
                        cache[(state, cur_sum)] = True  
                        return True  
            cache[(state, cur_sum)] = False  
            return False 
        total = sum(nums) 
        if total % k != 0:
            return False  
        target = total // k  
        nums.sort()  
        if nums[-1] > target:
            return False  
        return dfs(0, 0)

最后编辑于：2023.10.24 11:32:52

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,921评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,635评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,393评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,836评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,833评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,685评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,043评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,694评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,671评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,670评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,779评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,424评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,027评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,984评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,214评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,108评论 2赞 351
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,517评论 2赞 343

Day 28 回溯：93. 复原IP, 78|90. 子集 I II, 698. 划分为k个相等的子集

93. 复原 IP 地址

78. 子集

90. 子集 II

698. 划分为k个相等的子集

推荐阅读更多精彩内容