欢迎光临散文网 会员登陆 & 注册

回溯实操

2023-03-31 12:39 作者:raft0065  | 我要投稿

子集型回溯:

    每个元素都可以 选/不选

    当然这道题还可以参考[【Gosper's Hack】算法,可见链接:https://leetcode.cn/problems/maximum-rows-covered-by-columns/solution/by-endlesscheng-dvxe/


组合型回溯

    从 n 个数中选 k 个数的组合,可以看成是长度固定的子集。且相比子集型问题,组合型回溯可以做一些额外优化,即如果剩余个数不足,可以直接剪枝(倒序枚举,设 path 长为 m,那么还需要选 d=k-m 个数)


回溯实操的评论 (共 条)

分享到微博请遵守国家法律