首页 > 代码库 > 46. Permutations

46. Permutations

2024-09-15 04:43:08   208人阅读

题目：

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

 

Hide Tags
 Backtracking 

链接： http://leetcode.com/problems/permutations/

4/15/2017

6ms, 78%

按照之前backtracking的公式往上套，怎么都不对，忽然想起来这个permutation可能并不一样。

combination之类的在意的主要是元素，而permutation更在意元素＋顺序。所以在进入recursive之前就要让list里有所有元素，然后在recursive function中进行swap

注意第6，7行，第18，20行

再看一遍别人的答案，其实temp也可以不需要，直接在nums上进行位置互换就可以了。

 1 public class Solution {
 2     public List<List<Integer>> permute(int[] nums) {
 3         List<List<Integer>> ret = new ArrayList<>();
 4         ArrayList<Integer> temp = new ArrayList<Integer>();
 5         if (nums.length == 0) return ret;
 6         for (int i = 0; i < nums.length; i++) {
 7             temp.add(nums[i]);
 8         }
 9         enumerate(nums, ret, temp, 0);
10         return ret;
11     }
12     private void enumerate(int[] nums, List<List<Integer>> ret, ArrayList<Integer> temp, int pos) {
13         if (pos == nums.length) {
14             ret.add(new ArrayList<Integer>(temp));
15             return;
16         }
17         for (int i = pos; i < nums.length; i++) {
18             exchange(temp, pos, i);
19             enumerate(nums, ret, temp, pos + 1);
20             exchange(temp, i, pos);
21         }
22     }
23     private void exchange(ArrayList<Integer> temp, int i, int j) {
24         int tmp = temp.get(i);
25         temp.set(i, temp.get(j));
26         temp.set(j, tmp);
27     }
28 }

参考的是：

https://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/67CombinatorialSearch.pdf

别人的一个总结，但是我并不觉得总结得很好

https://discuss.leetcode.com/topic/46162/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partioning

另外一个别人的算法，用的是iterative，但是我不准备研究了

https://discuss.leetcode.com/topic/6377/my-ac-simple-iterative-java-python-solution

更多讨论：

https://discuss.leetcode.com/category/54/permutations

以及各种方法总结，值得看看next permutation

http://www.cnblogs.com/yrbbest/p/4436346.html

46. Permutations


联系
我们