0046. 全排列

[utterances-bot]

0046. 全排列 | 算法通关手册

https://algo.itcharge.cn/solutions/0001-0099/permutations/

[S1mpleBug]

附C++代码

这里给出两种解法，解法一采用回溯算法，🔗参考链接；解法二使用C++ STL算法库函数next_permutation

解法一：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void dfs(vector<int> &nums, vector<bool> &used) {
        if(tmp.size() == nums.size()) {
            res.push_back(tmp);
            return;
        }
        for(int i = 0; i < nums.size(); ++i) {
            if(used[i]) continue;
            tmp.push_back(nums[i]);
            used[i] = true;
            dfs(nums, used);
            tmp.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return {};
        vector<bool> used(n, false);
        dfs(nums, used);
        return res;
    }
};

解法二：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> tmp;
        do{
            tmp.clear();
            for(int i = 0; i < nums.size(); ++i)
                tmp.push_back(nums[i]);
            res.push_back(tmp);
        } while(next_permutation(nums.begin(), nums.end()));
        return res;
    }
};

[gentlewindt]

Java代码

class Solution {
    private List<List<Integer>> lists = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>(n);
        boolean[] used = new boolean[n];
        int count = 0;
        backtrace(list, used, count, nums);
        return lists;
    }

    public void backtrace(List<Integer> list, boolean[] used, int count, int[] nums) {
        // 到达决策树底端，将结果保存并返回
        if (count == nums.length) {
            lists.add(new ArrayList(list));
            return;
        }
        // 枚举可选元素列表
        for (int i = 0; i < used.length; i++) {
            // 选择没有出现的数字
            if (!used[i]) {
                // 选择元素
                list.add(nums[i]);
                // 标记
                used[i] = true;
                // 递归搜索
                backtrace(list, used, count + 1, nums);
                // 撤销选择
                list.remove(list.size() - 1);
                used[i] = false;
            }
        }
    }
}