TODO: 其他方法。
描述
Given a collection of distinct integers, return all possible permutations.
Example:
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]
]
|
分析
解决排列问题的方法有插入法，Johnson-Trotter 法，字典顺序法等等。
这里我们采用的易于理解的方式是递归加回溯，收敛的条件是递归到了最后一个元素。进行递归的时候，按照『字典序』，每次都选择一个没有出现过的元素。
解决方案1(Java)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums);
return result;
}
private void backtrack(List<List<Integer>> list, List<Integer> nowList, int[] nums) {
if (nowList.size() == nums.length) {
list.add(new ArrayList<>(nowList));
} else {
for (int i = 0; i < nums.length; i++) {
if (nowList.contains(nums[i])) {
continue;
}
nowList.add(nums[i]);
backtrack(list, nowList, nums);
nowList.remove(nowList.size()-1);
}
}
}
}
|
解决方案2（Golang）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| var result [][]int
func permute(nums []int) [][]int {
result = [][]int{}
backTrack(nums, len(nums), []int{})
return result
}
func backTrack(nums []int, numsLen int, path []int) {
if len(nums) == 0 {
now := make([]int, len(path))
copy(now, path)
result = append(result, path)
}
for i := 0; i < numsLen; i++ {
current := nums[i]
path = append(path, current)
nums = append(nums[:i], nums[i+1:]...)
backTrack(nums, len(nums), path)
nums = append(nums[:i], append([]int{current}, nums[i:]...)...)
path = path[:len(path)-1]
}
}
|
相关问题
References