花花酱 LeetCode 39. Combination Sum - 刷题找工作 EP81

[@HuaHuaLeetCode]

LeetCode 40: Combination Sum II kzbin.info/www/bejne/iITEpXRqqrt1erM

[@司曹龙]

花花师兄，我这有一个面试题没有很好的思路您能不能帮忙解答一下，k个有序数组，每个数组有n个元素，求它的中位数，实际复杂度好像要求的比较低，好像是二分思路，不过一直没有想明白

[@panwang7389]

谢谢花花的视频。从你的视频学了好多，对刷题帮助很大。这么多人讲题，你是讲的最清楚的，大赞！

[@jerryluo1989]

花花，可以搞一个DFS, Backtracking, Divide&Conquer, DFS+Memory 特辑么？

[@Emma-ru7kj]

youtube推荐从电影美妆到现在的花花酱 leetcode 刷题找工作. 希望大家都继续加油吧............

[@HuaHuaLeetCode]

加油！

[@boliu2410]

赞小结！希望花花老师以后有更多的规律总结的讲解，真是受益匪浅！

[@xicai2290]

根据花花的意思，这里d表示递归深度 slide里应该就是P(nums.size, n) 和 C(nums.size, n). 在nums中取n个数组成排列or组合。 其实这里我觉得也可以不用传递归深度，cur.size()可以直接表示递归深度。

[@HuaHuaLeetCode]

不用传，看新的78题的视频就没传。以前用pascal/c，要自己传d。

[@qingchuanlyu4605]

这一题好像把if candidates[i] > target: return 改成if candidates[i]

[@Andrew-eg2pc]

为什么这里DFS可以不需要用dynamic programming 的dictionary存储已经见过的combination list？不可以把已经见过的combination list存储在dictionary[remain] 里面？

[@lihu4659]

理论上降序排序的话就可以实现size递增的效果

[@suzdaniilya]

感谢花花酱解决我长久以来的迷思，一直搞不清楚permutation为什么要用set，combination和他长得那么像，之前面对dfs的题目一直是属于背代码，一直搞不清楚。感谢你 (虽然我现在在amazon😂)

[@wusuoyunhaiLS]

非常感谢花花！我还是有点不太明白什么要先排序，有没有大神可以帮忙解释下？

[@dannyhu202]

permutation中的调用递归函数少传了一个used参数

[@ray811030]

有人知道k-permutation, where k

[@furuolan]

excellent! Thanks so much Huahua! I will use your link to purchase amazon stuff to contribute.

[@andyhujian]

请问时间复杂度多少?如果网上找可以找出很多种答案，每个人的分析都有道理。

[@Jake_kumar]

O(2^n)

[@zhangjason1137]

对于输出结果需要从短到长列的情况，第一个for 循环是不要走一个完整的dfs才能找到 [7] ?

[@yuli3200]

请问solution set有多大？应该怎么分析？

[@dodocho8189]

其实第一个permutation 还是有点蒙,虽然可以大概理解.但是在递归返回的时候脑子有点乱.

[@dodocho8189]

划拉半天的递归返回递归返回, 才弄明白...

[@zezhixia9784]

这道题的time complexity和space complexity是多少呢

[@andyfu6534]

同问

[@sebastiangao6889]

这个挺难算的 我在另一个视频里看到的是 O(n^(target/min)) 和 O(target/min)

[@Bamboo_gong]

@@sebastiangao6889 视频能指下路吗

[@perkzzheng1708]

想问一下，cur 作为引用再进行dfs递归之后，再pop-back为什么可行?不是cur会改变吗？

[@yaqiwu3705]

你后来解决了吗，我写java也碰到了这个问题

[@emerylin6793]

cur 一直指向一个 object存当前状态的结果

[@jasonswift7468]

授人以渔👍

[@freddyzhou3130]

huahua 能給一下permutation combination的實現代碼嗎。。

[@ruizhenmai1194]

Permutation 可以参考他讲解的17题里的DFS

[@dodocho8189]

[@chendicao4491]

花花，我想问下这个讲义code是不是搞反了？permutation 不用记录 used boolean 吧，反而是 combination需要记录 used 因为不能重复。如果我搞错了，请帮忙更正我啊。谢谢！

[@yueranzhang2350]

permutation 需要 boolean来标记是因为不可以用重复元素, 比如不可以有(1,1,1), 所以用了1之后1就被标记为true. Combination不需要记录是因为for循环不是从0开始的 是从s+1开始的, 所以不会跟之前的s个元素产生重复

[@李泽鑫-c1v]

你好花花。请问这个思路的空间复杂度和时间复杂度应该怎么分析呢。谢谢。

[@HuaHuaLeetCode]

组合都是O(2^n) 空间 O(n)

[@cayenneshu]

拓展那块从短数组打印到长数组能不能先把数组按大到小牌 然后用原来的方法做

[@qichangzheng2716]

我觉得可以

[@shusenacademy]

嗯，排序之后其实更快一点点。

[@kannah4117]

这题可以不用递归方法么?

[@liweijian3589]

这个时间复杂度是2^n吗

[@lmnefg121]

您比我上的一些课程将的好多了。

[@nathann4291]

as an english speaker, how can i translate and understand this? thank you

[@nathann4291]

tnx Hang, so i am up and ready, and even a tool/software will do :)

[@kissinguramii]

请问楼主你视频里漂亮的表格是用viso画的吗？

[@HuaHuaLeetCode]

Wei Liu Google Slides

[@johanzhang7911]

花花你好, 如果把append(cur[:])改成append(cur), 结果为什么会变成空?

[@HuaHuaLeetCode]

cur退栈后会变成空数组，append的时候需要deep copy

[@airchen8904]

cur是指针引用 cur[:]是深拷贝 如果用cur 后续对cur操作 都会影响已经加入结果的cur

[@iriszheng3025]

老师现在在哪儿工作？

[@junminshi3928]

时间复杂度是n！吗？空间复杂度不考虑ans的话是多少？

[@HuaHuaLeetCode]

Junmin Shi 时间复杂挺难分析的… let s = target / min(nums[i]) T = C(s,1) + C(s, 2) + ... + C(s, s) = 2^s

[@HuaHuaLeetCode]

空间复杂度 O(target / min(nums[i]) )

[@furuolan]

花花棒

[@司曹龙]

真怕有一天不能翻墙了 不能看您的视频了 哈哈

[@HuaHuaLeetCode]

优酷/土豆/UC都有，虽然不是很全 i.youku.com/i/UMjcyMzg0NzY0OA==

[@司曹龙]

好，谢谢您

[@kma1138]

thx

[@李嘉伦-w2y]

讲的有点乱