LeetCode 46. Permutations

46. Permutations

Total Accepted: 147980
Total Submissions: 359083
Difficulty: Medium
Contributors: Admin

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

Subscribe to see which companies asked this question.

【题目分析】

给定一个整数数组，数组中的元素不重复出现。返回这些元素的所有可能的排列。

【思路】

1. 这事典型的用回溯算法来解决的题目。

2. 我们把元素分为已选的和未选的。每次的操纵就是从未选的元素中选择一个，然后把这一步选择这个元素的结果和这一步不选择这个元素的结果都找出来。

3. 为了标记元素被选择的状态，我们使用一个int数组

【代码】

 1 public class Solution {
 2     public List<List<Integer>> permute(int[] nums) {
 3         List<List<Integer>> list = new ArrayList<>();
 4         int[] used = new int[nums.length];
 5         backtrack(list, new ArrayList<>(), nums, used);
 6         return list;
 7     }
 8     
 9      private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int[] used){
10        if(tempList.size() == nums.length){
11           list.add(new ArrayList<>(tempList));
12           return;
13        }
14        for(int i = 0; i < nums.length; i++){ 
15           if(used[i] == 1) continue;
16           tempList.add(nums[i]);
17           used[i] = 1;
18           backtrack(list, tempList, nums, used);
19           tempList.remove(tempList.size() - 1);
20           used[i] = 0;
21        }
22    }
23 }