46. Permutations

zhaolu

　　题目：










　　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上进行位置互换就可以了。



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