Leetcode-46 Permutations

发表于 | 分类于 | 次

Permutations

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

Example 1

1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题思路

回溯法。如果排列中已经存在某元素，则跳过该元素。

复杂度分析

  • 时间复杂度：列举所有情况，$O(n^n)$。

  • 空间复杂度：调用栈最多为 n 层，$O(n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
	vector<vector<int>> res;
public:
	vector<vector<int>> permute(vector<int>& nums) {
		vector<int> sol;
		help(nums, sol);
		return res;
	}

	void help(vector<int> &nums, vector<int> &sol) {
		if (sol.size() == nums.size()) {
			res.push_back(sol);
			return;
		}
		for (int i : nums) {
			if (find(sol.begin(), sol.end(), i) == sol.end()) {
				sol.push_back(i);
				help(nums, sol);
				sol.pop_back();
			}
		}
	}
};