Permutations

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].

Analysis 1

• index：指向每次要插入的元素
• 通过循环每次把index指向的元素插入到所有可能的位置

1. index = 0, i=0
   在0位置插入nums[0]，得到[1]
2. index = 1, i=0, 1
   在0，1位置插入nums[1],得到[2,1]和[1,2]
3. index = 2, i=0, 1, 2
   在0，1，2位置插入nums[2]，得到[3,2,1] [2,3,1] [2,1,3] [3,1,2] [1,3,2] [1,2,3]


                        [1]
                /                  \
         [2,1]                       [1,2]
    /      |      \              /     |      \
[3,2,1] [2,3,1] [2,1,3]     [3,1,2] [1,3,2] [1,2,3]

Code 1

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length==0) {return result;}
        List<Integer> list = new ArrayList<Integer>();
        dfs(nums, result, list, 0);
        return result;
    }

    private void dfs(int[] nums, List<List<Integer>> result, List<Integer> list, int index){
        if (list.size() == nums.length){
            result.add(list);
            return;
        }

        for (int i=0; i<=list.size(); i++){
            List<Integer> copy = new ArrayList<Integer>(list);
            copy.add(i,nums[index]);
            dfs(nums, result, copy, index+1);
        }
    }
}

Analysis 2

• 这种方法和 Permutations II 更加consistent
• 注意该方法要求nums里的值都是unique的
• for 循环每次从头到尾扫描，只要以前没有的，就加入
• 每次call contains感觉效率没有上一中方法高

      [1]                [2]                 [3]
 [1,2]   [1,3]      [2,1]   [2,3]       [3,1]   [3,2]
[1,2,3] [1,3,2]    [2,1,3] [2,3,1]    [3,1,2] [3,2,1]

Code 2

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) return result;

        List<Integer> list = new ArrayList<Integer>();
        dfs(nums, list, result);

        return result;
    }

    private void dfs(int[] nums, List<Integer> list, List<List<Integer>> result) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) continue;
            list.add(nums[i]);
            dfs(nums, list, result);
            list.remove(list.size() - 1);
        }
    }
}

Reference

Code 1: Leetcode
Code 2: Yuanbin