46. Permutations 全排列

[GH1995]

46. Permutations

Difficulty: Medium

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Solution

Language: C++

class Solution {
 public:
  vector<vector<int>> permute(vector<int> &nums) {
    vector<vector<int>> result;
    vector<int> path;
​
    backtrack(result, path, nums);
​
    return result;
  }
​
  void backtrack(vector<vector<int>> &result, vector<int> &path,
                 vector<int> &nums) {
    if (path.size() == nums.size())
      result.push_back(path);
    else {  // 如果元素没满，就不断地往里面加元素
      for (int i = 0; i < nums.size();
           ++i) {  //加元素是从nums 0->n-1加，只要检测有没有包含就行
        if (find(path.begin(), path.end(), nums[i]) != path.end())
          continue;  // element already exists, skip
        path.push_back(nums[i]);
        backtrack(result, path, nums);
        path.pop_back();
      }
    }
  }
};

[GH1995]

需要一个visit数组记录

状态visit, path,

1. 状态是什么？ (result, path, nums)

2. 如何扩展状态？

   for nums[i] in nums:
   if (nums[i] not in apth)
       ([[]], [], nums) -> ([[]], path + nums[i], nums)

3. 临界条件是什么？元素已满

4. 剪枝条件是什么？无

5. 判重条件？在原来的队列里出现过