[leetcode]46. Permutations全排列(给定序列无重复元素)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Given a collection of distinct integers, return all possible permutations.

Input: [1,2,3]

Output:

[

  [1,2,3],

  [1,3,2],

  [2,1,3],

  [2,3,1],

  [3,1,2],

  [3,2,1]

]

题意：

打印全排列

Solution1: Backtracking

形式化的表示递归过程： permutations(nums[0...n-1]) = {取出一个数字} + permutations(nums[0...n-1] - 该数字)

code

 /*

 Time: O(n!)

 Space: O(n!). We allocate space to keep N! paths.

 */

 class Solution {

     public List<List<Integer>> permute(int[] nums) {

         List<List<Integer>> result = new ArrayList<>();

         // corner case

         if (nums == null || nums.length == 0) return result;

         List<Integer> path = new ArrayList<>();

         helper(nums, path, result);

         return result;

     }

     private void helper(int[] nums, List<Integer> path, List<List<Integer>> result){

         // base case

         if(path.size() == nums.length){

             result.add(new ArrayList<>(path));

             return;

         }

         for(int i = 0; i< nums.length; i++){

             if(path.contains(nums[i])) continue;

             path.add(nums[i]);

             helper(nums, path, result);

             path.remove(path.size() - 1);

         }

     }

 }