花花 我在python做的时候 直接ans.append(cur) 没有copy 然后递归语句dfs(n, i+1,cur+[nums[i]]) 前后没有cur的进退栈操作 也通过了。 能讲解下append(cur.copy()) 为什么用copy 配合cur的进出栈么？ class Solution: def subsets(self, nums): ans = [] def dfs(n, s, cur): if n == len(cur): ans.append(cur.copy()) return for i in range(s, len(nums)): cur.append(nums[i]) dfs(n, i + 1, cur) cur.pop() for i in range(len(nums) + 1): dfs(i, 0, []) return ans
md笔记，cpp实现排列组合，分为有重复值和无重复值，结果存在ans中。该程序没有输出。。 ---------------- #### - Combination (without duplicates) ```cpp #include "iostream" #include "vector" using namespace std; /** * int n: the number of candidates * int s: the start position, first calling is 0 normally * cur: to store a current combination * ans: to store final combinations list */ void dfs(const vector &nums, int n, int s, vector &cur, vector &ans) { if (n == cur.size()) // the size of cur is dynamic changing... { ans.push_back(cur); return; } for (int i = s; i < nums.size(); ++i) { cur.push_back(nums[i]); dfs(nums, n, i + 1, cur, ans); cur.pop_back(); } } int main() { vector nums = {0, 1, 2}; vector ans; vector cur; // C32, 2 is the cadidates nums dfs(nums, 2, 0, cur, ans); return 0; } ``` #### - Permutation (without duplicates) ```cpp #include "iostream" #include "vector" using namespace std; void dfs(const vector &nums, int n,vector &cur, vector &ans, vector &used) { if (n == cur.size()) { ans.push_back(cur); return; } for (int i = 0; i < nums.size(); ++i) { if (used[i]) continue; used[i] = 1; cur.push_back(nums[i]); dfs(nums, n, cur, ans, used); cur.pop_back(); used[i] = 0; } } int main() { vector nums = {0, 1, 2}; vector ans; vector cur; vector used(nums.size(), 0); // A 32 dfs(nums, 2, cur, ans, used); return 0; } ``` #### - Combination (has duplicates) > 1. sort array within `main()` function > 2. add condition `if(i>s && nums[i] == nums[i-1]) continue;` to frist line within for loop. > 3. you need to add `#include ` and ``sort(nums.begin(), nums.end());`` #### - Permutaion (has duplicates) > 1. sort array within `main()` function > 2. add condition `if(used[i] || i>0 && nums[i] == nums[i-1] && !used[i]) continue;` to frist line within for loop.
可以这样打log查看递归回溯过程 ----------- #include "iostream" #include "vector" using namespace std; vector subsets(vector &nums); void dfs(const vector &nums, int n, int s, vector &cur, vector &ans); void debugging(vector &cur); /** * int n: the number of candidates * int s: the start position, first calling is 0 normally * cur: to store a current combination * ans: to store final combinations list */ void dfs(const vector &nums, int n, int s, vector &cur, vector &ans) { if (n == cur.size()) // the size of cur is dynamic changing... { ans.push_back(cur); cout
![[7 Methods] LeetCode 287 Find the Duplicate Number - 花花酱 刷题找工作 EP406](/img/n.gif)
花花这里combination解法redundancy太高了 对于每次不同长度的subset，结果的生成总是需要build from the scratch， 即从空subset开始。 这样算下来整个Time Complexity 是远远大于 O（N*2^N）的。
这样即可， 每到一个节点，基于当前的curr，遍历所有可以append 新元素的情况 （当然，也需要back track一下），当数组扫到底的时候，其实自然就会停止了：
def backtracking(nums, i, curr):
res.append(curr[:]) # shallow copy
for idx in range(i, len(nums)):
curr.append(nums[idx])
backtracking(nums, idx+1, curr)
curr.pop()
res = []
backtracking(nums, 0, [])
return res
别人的解法和huahua的其实是有些不同的， 1.花花的 解法 的base case是 if(cur.size() == k), 但是别人的写法 是 没有base case的, 直接进入 dfs() function里面， 就把cur 加到 res里面。 他们的想法 相当于 把 recursion tree的每一个node 都加到 res 里面。但我个人喜欢花花的解法。 因为更说的通。
為什麼要starting point啊
这样解c(m, n+1) 的时候是不是要把c(m,n)的结果又从头遍历一遍？
感谢讲解！花花太强啦。
Thanks! Merry Christmas! Wish you and your family all the best!
LC78题的解法怎么扩展到LC90题（Subsets II）？这两题我只会迭代。。。
花花的解法是基于Combination的代码实现的。相当于C(N, 0) + C(N, 1) + ... + C(N, N)，查了下数学上确实等于2^N，神奇的数学。缺点是好像会稍微慢一点，就跟楼下有个同学说的一样，解C(N, N)的时候会重复走完之前所有depth的每个Node。看见另一个被广泛使用的写法是直接求解深度为depth的所有combination，DFS没有终止条件，直接把路过的所有Node全部append，走过哪个Node就append哪个Node，跟另一个说得同学一样，是穷尽所有recursion branches然后停止的。个人觉得后一种解法很奇怪，花花的解法更严谨。
讲的很清楚，谢谢
谢谢~冬至快乐&Merry Christmas~！
打卡打卡 花花酱辛苦了
有一个想不通的问题，为什么那个地方要用cur.copy(), 我试了直接ans.append(cur)最终ans里面加入的全都是空的list. 但是list.append()不是就是加value进去吗？
append是shallow copy, 由于cur一直在被被修改，所以这里需要deep copy。
@@HuaHuaLeetCode 所以说append的时候是append了cur的地址，而不是他的value？是不是只要操作list都是地址
@@Ivan-ek6kg 可以这么认为，但本质上存是一个shallow copy，并不是地址/指针。因为python中的int/float什么的也是object，他们的shallow copy的效果等价于deep copy，得到的结果就像是存了value一样，其实是两个完全不同的objects…
@@HuaHuaLeetCode 好的，非常感谢
Approach1 是 BFS 吧
dfs
花花 我在python做的时候 直接ans.append(cur) 没有copy 然后递归语句dfs(n, i+1,cur+[nums[i]]) 前后没有cur的进退栈操作 也通过了。 能讲解下append(cur.copy()) 为什么用copy 配合cur的进出栈么？
class Solution:
def subsets(self, nums):
ans = []
def dfs(n, s, cur):
if n == len(cur):
ans.append(cur.copy())
return
for i in range(s, len(nums)):
cur.append(nums[i])
dfs(n, i + 1, cur)
cur.pop()
for i in range(len(nums) + 1):
dfs(i, 0, [])
return ans
因为 cur+[nums[i]] 创建了一个新的对象... 时间复杂度 从 O(n*K) 变为 O(n^2* K)
@@HuaHuaLeetCode谢谢回复！
这个时间复杂度不是应该跟常规的combination一样吗, 不应该是O(2^n)吗？
一共有2^n个subset，每个subset需要花费O(n)的时间。
@@HuaHuaLeetCode 这道题的discussion vote最多的解跟花花的其他combination题的解看起来差不多， 都是没有subsets function里的for loop. 我推演了一下他的时间复杂度，感觉是O(2^n). 而且花花你的解里的dfs 里的for loop 到i
@@HuaHuaLeetCode 请问为什么每个subset要话费O(n)时间？
copy
@@HuaHuaLeetCode 谢谢
md笔记，cpp实现排列组合，分为有重复值和无重复值，结果存在ans中。该程序没有输出。。
----------------
#### - Combination (without duplicates)
```cpp
#include "iostream"
#include "vector"
using namespace std;
/**
* int n: the number of candidates
* int s: the start position, first calling is 0 normally
* cur: to store a current combination
* ans: to store final combinations list
*/
void dfs(const vector &nums, int n, int s, vector &cur, vector &ans)
{
if (n == cur.size()) // the size of cur is dynamic changing...
{
ans.push_back(cur);
return;
}
for (int i = s; i < nums.size(); ++i)
{
cur.push_back(nums[i]);
dfs(nums, n, i + 1, cur, ans);
cur.pop_back();
}
}
int main()
{
vector nums = {0, 1, 2};
vector ans;
vector cur;
// C32, 2 is the cadidates nums
dfs(nums, 2, 0, cur, ans);
return 0;
}
```
#### - Permutation (without duplicates)
```cpp
#include "iostream"
#include "vector"
using namespace std;
void dfs(const vector &nums, int n,vector &cur, vector &ans, vector &used)
{
if (n == cur.size())
{
ans.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (used[i]) continue;
used[i] = 1;
cur.push_back(nums[i]);
dfs(nums, n, cur, ans, used);
cur.pop_back();
used[i] = 0;
}
}
int main()
{
vector nums = {0, 1, 2};
vector ans;
vector cur;
vector used(nums.size(), 0);
// A 32
dfs(nums, 2, cur, ans, used);
return 0;
}
```
#### - Combination (has duplicates)
> 1. sort array within `main()` function
> 2. add condition `if(i>s && nums[i] == nums[i-1]) continue;` to frist line within for loop.
> 3. you need to add `#include ` and ``sort(nums.begin(), nums.end());``
#### - Permutaion (has duplicates)
> 1. sort array within `main()` function
> 2. add condition `if(used[i] || i>0 && nums[i] == nums[i-1] && !used[i]) continue;` to frist line within for loop.
可以这样打log查看递归回溯过程
-----------
#include "iostream"
#include "vector"
using namespace std;
vector subsets(vector &nums);
void dfs(const vector &nums, int n, int s, vector &cur, vector &ans);
void debugging(vector &cur);
/**
* int n: the number of candidates
* int s: the start position, first calling is 0 normally
* cur: to store a current combination
* ans: to store final combinations list
*/
void dfs(const vector &nums, int n, int s, vector &cur, vector &ans)
{
if (n == cur.size()) // the size of cur is dynamic changing...
{
ans.push_back(cur);
cout
Combination解法是 BFS过程吧
DFS for sure here. But, there's BFS sol
能解释下为什么时间复杂度是n*2的n次方么, 如何理解cur.pop() ?
因为是在一个for循环中，比如 cur + nums[s] = [1, 2], next iteration, cur = [1] --> add nums[s] = [1, 3]
花花什么时刻可以开一个bitwise的专题阿, s &( 1
Yesssss
花花什么时候能讲一下这类问题的时间复杂度和空间复杂度分析么？这两类题的时间复杂度我一直很难分析清楚，看了很多discussion，似乎很难看到有人把这个问题讲清楚过。还有和recursion相关的时间复杂度和空间复杂度感觉分析起来有点吃力呢。
combination O(n*2^n)
permutation O(n*n!)
感谢感谢！@@HuaHuaLeetCode
@@HuaHuaLeetCode 请问这道subset用dfs的复杂度是O(2^n)吗？调用没有求(m, n)直接求全组合，你另外一道特辑里讲的也是O(2^n)
这个完全没听懂
按照介绍画了一下图，懂了。