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

/*搜索与回溯一般可以分为六大步
1.枚举
2.是否标记
3.没有则标记
4.搜索
5.回溯（还原状态），类似与悔棋
6.判断结束条件
*/
class Solution {
public:
    /**
     * 生成数字的所有排列
     * @param num int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > permute(vector<int>& num) {
        vector<vector<int>> result;
        vector<int> current;
        vector<bool> used(num.size(), false);
        
        backtrack(num, current, used, result);
        return result;
    }
    
    // 回溯函数：生成所有排列
    void backtrack(const vector<int>& num, vector<int>& current, 
                  vector<bool>& used, vector<vector<int>>& result) {
        // 当当前排列长度等于原数组长度时，说明找到了一个完整排列（6.判断结束条件）
        if (current.size() == num.size()) {
            result.push_back(current);
            return;
        }
        
        // 尝试每个未使用的数字（1.枚举）
        for (int i = 0; i < num.size(); ++i) {
            if (!used[i]) {//（2.是否标记）
                // 选择当前数字
                used[i] = true;//（3.标记）
                current.push_back(num[i]);//（4.搜索）
                
                // 递归处理下一个位置
                backtrack(num, current, used, result);
                
                //（5.回溯：撤销选择）
                current.pop_back();
                used[i] = false;
            }
        }
    }
};