全排列

image.png

要点：
回溯法模版
组合问题：使用startIndex, for循环每层从startIndex开始 标识为skip 重复的路径；
排列问题：使用used 数组记录使用情况，for循环每层从0开始，根据used 标识为skip 选择

/*
 *数据结构
 */
void backtracking(vector<int>& nums)
{
  if (中止条件）{
    保存结构
    return;
  }

  int i;
  for(i=0; i<nums.size();i++){
    if(used[i]) continue;

    used[i]=true;
    path.push_back(nums[i]);
    backtracking(nums);
    path.pop_back();
    used[i]=false;

  }

}

class Solution {
public:
    vector<int > path;
    vector<vector<int>> result;
    
    void backtracking(vector<int>& nums, vector<bool>& used)
    {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for(int i=0; i< nums.size(); i++ ) {
            if (used[i]) continue;

            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {

        vector<bool > used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};