- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
回溯
你爱，或者不爱我。爱就在那里，不增不减。
- 对于数组中的每个元素都有两种选择：选或者不选。
- 对于当前迭代的元素，选择它就将其 push 后，基于选择后的状态从
start + 1递归。 - 然后使用 pop 将其状态恢复，不选择当前迭代的元素从
start + 1递归。
constsubsets=function(nums)=>{constres=[]constdfs=function(start,cur){if(start===nums.length){res.push(cur.slice())return}cur.push(nums[start])// 选择dfs(start+1,cur)cur.pop()dfs(start+1,cur)// 不选择}dfs(0,[])returnres}
- 时间复杂度: O(n * 2^n)，共 2^n 个状态，需要 O(n) 的时间来构造子集。
- 空间复杂度: O(n)