题解 | 没有重复项数字的全排列

class Solution {
public:
    vector<vector<int>> permute(vector<int>& num) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(num.size(), false); // 标记元素是否被使用过
        backtrack(num, used, path, result);
        return result;
    }

private:
    void backtrack(vector<int>& num, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) {
        // 当路径长度等于数组长度时，说明找到一个排列
        if (path.size() == num.size()) {
            result.push_back(path);
            return;
        }
        
        // 遍历所有可能的选项
        for (int i = 0; i < num.size(); i++) {
            // 如果当前数字已经被使用过，跳过
            if (used[i]) {
                continue;
            }
            
            // 做选择
            used[i] = true;
            path.push_back(num[i]);
            
            // 递归进入下一层决策树
            backtrack(num, used, path, result);
            
            // 撤销选择（回溯）
            path.pop_back();
            used[i] = false;
        }
    }
};

也可以用官方题解的交换来实现递归和回溯
class Solution {
public:
    void recursion(vector<vector<int> > &res, vector<int> &num, int index){
        //分枝进入结尾，找到一种排列
        if(index == num.size() - 1) 
            res.push_back(num);
        else{
            //遍历后续的元素
            for(int i = index; i < num.size(); i++){ 
                //交换二者以获得不同排列
                swap(num[i], num[index]); 
                //继续往后找
                recursion(res, num, index + 1); 
                //回溯
                swap(num[i], num[index]); 
            }
        }
    }
    
    vector<vector<int> > permute(vector<int> &num) {
        //先按字典序排序
        sort(num.begin(), num.end()); 
        vector<vector<int> > res;
        //递归获取
        recursion(res, num, 0); 
        return res;
    }
};