【三十三】【算法分析与设计】回溯（1），46. 全排列，78. 子集，没有树结构，但是依旧模拟树结构，回溯，利用全局变量+递归函数模拟树结构

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1，2，3] 输出：[[1，2，3]，[1，3，2]，[2，1，3]，[2，3，1]，[3，1，2]，[3，2，1]]

示例 2：

输入：nums = [0，1] 输出：[[0，1]，[1，0]]

示例 3：

输入：nums = [1] 输出：[[1]]

提示：

1 <= nums.length <= 6

-10 <= nums[i] <= 10

nums 中的所有整数 互不相同

定义dfs递归函数，当前树的所有有效序列填充到 ret 数组。

定义ret数组存储全排列序列。

定义path存储根节点到当前节点的路径。

定义check数组，存储当前节点哪些元素是我们的孩子节点，哪些元素不是我们的孩子节点。

维护dfs递归函数内部逻辑，第一个位置选择一个孩子节点作为路径，然后将子树的所有有效序列填充到ret数组中。

递归函数的出口，当path.size()==nums.size()，ret.push_back(path); return;

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    vector<bool> check;

public:
    vector<vector<int>> permute(vector<int>& nums) {
        check.resize(7);
        dfs(nums);
        return ret;
    }
    void dfs(vector<int>& nums) {
        if (path.size() == nums.size()) {
            ret.push_back(path);
            return;
        }

        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (!check[i]) {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的

子集

（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1，2，3] 输出：[[]，[1]，[2]，[1，2]，[3]，[1，3]，[2，3]，[1，2，3]]

示例 2：

输入：nums = [0] 输出：[[]，[0]]

提示：

1 <= nums.length <= 10

-10 <= nums[i] <= 10

nums 中的所有元素 互不相同

第一个位置元素选或者不选，第二个位置元素选或者不选，以此类推。

定义dfs将数中所有有效节点填充到ret数组中，i表示当前节点是否选择i位置元素。

定义ret数组存储子集序列。

定义path存储根节点到当前节点的路径。

维护dfs递归内部逻辑，对于 i 位置的元素，选或者不选，如果不选，将子树的所有有效序列填充到ret数组中。

如果选，将子树的所有有效序列填充到ret数组中。

选与不选的时候，将i++传入下一个节点，此时在本次的节点中，依旧需要维护 i 的意义，所以dfs后都需要 i--操作。

如果dfs不传引用，就不需要主动i--操作，系统自动维护 i 的意义。

选择之后在当前的节点中，还需要维护path的意义。

递归的出口，当i==nums.size()，ret.push_back(path); return;

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path; // 根节点到当前节点的路径
    vector<vector<int>> subsets(vector<int>& nums) {
        // 定义dfs递归函数填充ret
        int i=0;
        dfs(nums, i);
        return ret;
    }

    void dfs(vector<int>& nums, int& i) {
        if (i == nums.size()) {
            ret.push_back(path);
            return;
        }
        // 不选
        dfs(nums, ++i);
        i--;
        // 选
        path.push_back(nums[i]);
        dfs(nums, ++i);
        i--;
        path.pop_back();
    }
};

子集的元素有零个，一个，两个，以此类推。

定义dfs递归函数，将树中每一个节点都填充到ret数组中，pos表示子树节点添加的数字的开始下标。

定义path存储当前节点的序列。

定义ret存储子集序列。

递归函数内部逻辑，首先将path添加到ret数组中。然后进入下一个节点当中，维护path，和pos。

递归出口，在维护完ret后，如果pos==nums.size()此时返回return。

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path; 
    vector<vector<int>> subsets(vector<int>& nums) {
        // 定义dfs递归函数填充ret
        int pos = 0;
        dfs(nums, pos);
        return ret;
    }

    void dfs(vector<int>& nums, int pos) {
        ret.push_back(path);
        if (pos == nums.size())
            return;
        for (int i = pos; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
};