46. Permutations
题目：Given a collection of numbers, return all possible permutations.
For example,
have the following permutations:
, , , , , and .
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上进行位置互换就可以了。
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
ArrayList<Integer> temp = new ArrayList<Integer>();
if (nums.length == 0) return ret;
for (int i = 0; i < nums.length; i++) {
temp.add(nums);
}
enumerate(nums, ret, temp, 0);
return ret;
}
private void enumerate(int[] nums, List<List<Integer>> ret, ArrayList<Integer> temp, int pos) {
if (pos == nums.length) {
ret.add(new ArrayList<Integer>(temp));
return;
}
for (int i = pos; i < nums.length; i++) {
exchange(temp, pos, i);
enumerate(nums, ret, temp, pos + 1);
exchange(temp, i, pos);
}
}
private void exchange(ArrayList<Integer> temp, int i, int j) {
int tmp = temp.get(i);
temp.set(i, temp.get(j));
temp.set(j, tmp);
}
}
4/22/2017
算法班
算法班是通过不断判断是否元素已存在，若不存在加入新的值，处理后减去加入的值来做的。注意主函数中并不需要事先把元素都放进去
class Solution {
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public List<List<Integer>> permute(int[] nums) {
// write your code here
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
if (nums == null || nums.length == 0) {
result.add(list);
return result;
}
search(nums, list, result);
return result;
}
public void search( int[] nums,
List<Integer> list,
List<List<Integer>> result) {
if (list.size() == nums.length) {
result.add(new ArrayList(list));
}
for (int i = 0; i < nums.length; i++) {
if (list.contains(nums)) {
continue;
}
list.add(nums);
search(nums, list, result);
list.remove(list.size() - 1);
}
return;
}
}
参考的是：
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
页:
[1]