2018年4月13日 下午3:54
Subsets - LeetCode
回忆一下
分析：
- 这个问题里理解item是最关键的问题
- 我们在上面几节的学习中没有涉及到递归，很多题总结下来本质就是一个数组的遍历，当然在不同的情况下，遍历的目的不同，可能是为了统计，可能是为了迭代出一个结果。
- 在这道递归的题中，我理解下来其实也是一个遍历数组的问题，eg遍历[1,2,3]。不使用递归时，我们有一个指针，通过这个指针去一个个的遍历，在递归中，我们每次调用递归函数，在调用的时候参数i++，其实就是指针的作用。
- 在非递归中，我们统计、迭代、记录过程，在递归中我们也会统计、迭代、记录过程。
- 在这道题中，item其实就是一个“统计记录”。记录着我们当前操作到了哪里。
- 他们最大的不同是：一次递归函数中调用了两次generate()函数，这就说明对同一个位置进行两次的操作。在非递归中我们一般对同一个位置只处理一次，因为一个循环是一个单线程，你无法同时让他们对一个位置的数据同处理。递归就提供了这种假的同时处理的可能。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
std::vector<int> item;
result.push_back(item);
generate(result, 0, nums, item);
return result;
}
private:
//表面的一层
void generate(std::vector<std::vector<int>> &result, int i, std::vector<int> nums,std::vector<int> item ){
if(i >= nums.size()){
return ;
}
//nums[i]放进入
item.push_back(nums[i]);
result.push_back(item);
generate(result, i+1, nums, item );
//nums[i]不放进入
item.pop_back();
generate(result, i+1, nums, item );//当到达右下角时，我们不放3，执行这里。结果直接返回了，那么[]空就没有放进入，需要我们自己手动的放
}
};