LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• STL 提供了计算全排列下一排列的 std::next_permutation 和计算全排列上一排列的 std::prev_permutation

class Solution {
 public:
  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    sort(begin(nums), end(nums));
    do {
      res.emplace_back(nums);
    } while (next_permutation(begin(nums), end(nums)));
    return res;
  }
};

• 常规做法是回溯法

class Solution {
 public:
  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    dfs(res, nums, 0);
    return res;
  }

  void dfs(vector<vector<int>>& res, vector<int>& nums, int n) {
    if (n == size(nums)) {
      res.emplace_back(nums);
      return;
    }
    for (int i = n; i < size(nums); ++i) {
      swap(nums[i], nums[n]);
      dfs(res, nums, n + 1);
      swap(nums[i], nums[n]);
    }
  }
};