46. 全排列

46. 全排列 - 力扣（LeetCode）

class Solution {
  vector<vector<int>> Result;
  vector<int> Current;
  vector<int> Used;
  void Backtrack(vector<int> &Nums) {
    if (Current.size() == Nums.size()) {
      Result.emplace_back(Current);
      return;
    }

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

      Used[i] = true;
      Current.push_back(Nums[i]);
      Backtrack(Nums);
      Current.pop_back();
      Used[i] = false;
    }
  }

public:
  vector<vector<int>> permute(vector<int>& nums) {
    int N = nums.size();
    Current.reserve(N);
    // XXX reserve() DOESN'T change the end() of vector!!!
    // Used.reserve(N);
    Used.resize(N);
    std::fill(Used.begin(), Used.end(), false);

    Backtrack(nums);

    return Result;
  }
};

我操了，他妈的 reserve() 和 resize() 不是一个东西啊，reserve() 是不改变 end() 位置的！我就说怎么写半天发现 Flag[i] 总是真、Current 总是空的……我服了。

说实话，既然有哈希表那对于 flag 位的标记可能还是直接用哈希表比较合适。我到底是怎么鬼迷心窍地想去用那个 vector 的。

class Solution {
  vector<vector<int>> Result;
  vector<int> Current;
  unordered_map<int, bool> Used;
  void Backtrack(vector<int> &Nums) {
    if (Current.size() == Nums.size()) {
      Result.emplace_back(Current);
      return;
    }

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

      Used[i] = true;
      Current.push_back(Nums[i]);
      Backtrack(Nums);
      Current.pop_back();
      Used[i] = false;
    }
  }

public:
  vector<vector<int>> permute(vector<int>& nums) {
    Backtrack(nums);
    return Result;
  }
};

此外，回溯问题的统一模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择 : 本层集合中的元素) {
        处理节点;
        backtracking(路径, 选择列表); // 递归
        撤销处理; // 回溯
    }
}

二刷 

class Solution {
  vector<int> Visited_;
  vector<int> Current_;
  vector<vector<int>> Result_;

  void DFS(vector<int> &V, int Remaining) {
    if (Remaining == 0) {
      Result_.emplace_back(Current_);
      return;
    }

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

      Visited_[i] = true;
      Current_.emplace_back(V[i]);
      DFS(V, Remaining - 1);
      Current_.pop_back();
      Visited_[i] = false;
    }
  }
 
public:
  vector<vector<int>> permute(vector<int>& nums) {
    // Visited_.reserve(nums.size());
    // std::fill(Visited_.begin(), Visited_.end(), 0);
    Visited_.resize(nums.size());

    DFS(nums, nums.size());
    return Result_;
  }
};

我操，又是这个reserve()的问题，以后不管怎么样直接resize()好了，甚至还有默认构造，为什么不用呢。

还有就是注意不动点的问题。其实按理来说这题并不需要单独设立一个Remaining参数作为不动点，因为我们完全可以用Current.size() == Nums.size()的谓词来判断。