leetcode46.Permutation

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
Given a collection of distinct 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],
  [3,2,1]
]

也就是得出所有可能的排列组合结果

解题思路和代码

这题显然采用递归的思路。例如，如果我们知道两个元素所有排列组合的结果，那么在该排列组合的结果上加入第三个元素，只需将第三个元素插入双元素排列组合结果的不同位置上即可以生成三个元素排列组合的结果。四个元素同理。
在这里，我采用LinkedList实现队列，从队列头获得上一组的结果，和当前元素结合之后，将结果插入到队尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<List<Integer>> permute(int[] nums) {
    LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();
    if(nums.length == 0){
        return result;
    }
    List<Integer> first = new LinkedList<Integer>();
    first.add(0, nums[0]);
    result.add(first);
    List<Integer> temp;
    for(int i = 1 ; i<nums.length ; i++){
        int number = nums[i];
        do{
            temp = result.removeFirst();
            for(int j = 0 ; j <=temp.size() ; j++){
                temp.add(j, number);
                result.add(new LinkedList<Integer>(temp));
                temp.remove(j);
            }
        }while(result.getFirst().size() == i);
    }
    return result;
}