全排列+力扣

题目

题目链接

. - 力扣（LeetCode）

题目描述

代码实现

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
    bool used[7];
public:
    vector<vector<int>> permute(vector<int>& nums) {
        _permute(nums);
        return ret;
    }
    void _permute(vector<int>& nums){
        if(nums.size() == path.size()){
            ret.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); ++i){
            if(used[i] == false){
                path.push_back(nums[i]);
                used[i] = true;
                _permute(nums);
                //回溯
                path.pop_back();
                used[i] = false;
            }
        }
    }
};

思路分析

1、全排类就是类似于暴搜，所有合适的组合一遍。

2、首先我我们需要一个数组path，将每次结果放到二维数组ret中。

3、其次我们在组合的过程中，有些已经用过的数字便不能参加下次的运算。因此需要使用一个used数组标识该数字是否被使用过。

4、当数字未被使用过就添加到path中，在将此数字标记为使用，即used[i]=true，进入下一轮组合。回溯的时候，就将该数字从path中移除，并将该数字标记为false。

5、最后考虑递归出口，当path中的元素和nums中的元素个数相等时，即可将path添加到ret二维数组中，再return。

如下决策树，只画了部分，仅供参考。