LeetCode 78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解析：
根据给定的数组，列出数组元素所有子集情况。
解法1:
非递归法
依次遍历数组中的元素，然后一位一位的往上叠加，比如对于题目中给的例子 [1,2,3] 来说，最开始是空集，那么我们现在要处理1，就在空集上加1，为 [1]，现在我们有两个自己 [] 和 [1]，下面我们来处理2，我们在之前的子集基础上，每个都加个2，可以分别得到 [2]，[1, 2]，那么现在所有的子集合为 [], [1], [2], [1, 2]，同理处理3的情况可得 [3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合了
代码如下：
[cc lang=”C++”]
class Solution {
public:
vector<vector> subsets(vector& nums) {
vector<vector> result(1);
for(int i=0; i < nums.size(); i++) { int size = result.size(); for(int j=0; j < size; j ++) { result.push_back(result[j]);//先获取已有结果 result.back().push_back(nums[i]);//在已有结果上追加当前元素 } } return result; } }; [/cc]

2.回溯法

回溯算法的基本形式是“递归+循环”，正因为循环中嵌套着递归，递归中包含循环，这才使得回溯比一般的递归和单纯的循环更难理解，其实我们熟悉了它的基本形式，就会觉得这样的算法难度也不是很大。原数组中的每个元素有两种状态：存在和不存在。 ① 外层循环逐一往中间集合 temp 中加入元素 nums[i]，使这个元素处于存在状态 ② 开始递归，递归中携带加入新元素的 temp，并且下一次循环的起始是 i 元素的下一个，因而递归中更新 i 值为 i + 1 ③ 将这个从中间集合 temp 中移除，使该元素处于不存在状态

具体代码如下：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> ans;
        dfs(nums, 0, result, ans);
        return result;
    }
    void dfs(vector<int>& nums, int i, vector<vector<int>>& result, vector<int>& ans)
    {
        result.push_back(ans);
        for(int j=i; j < nums.size(); j++)
        {
            ans.push_back(nums[j]);
            dfs(nums, j+1, result, ans);
            ans.pop_back();
        }
    }
};

运行结果：
参考：
https://www.cnblogs.com/grandyang/p/4309345.html
https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51604217</vector</vector</vector</vector</vector