Leetcode46——Permutations

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. 问题描述

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

2. 求解

递归法

这道题是求数组的全排列，首先可以用递归法，第一次往链表添加一个元素，有n中可能，然后将剩下的元素再添加一个元素到链表中，有n-1种可能，以此类推，直至链表中的元素大小等于数组大小。

public class Solution {
    public static List<List<Integer>> result = new ArrayList<List<Integer>>();public List<List<Integer>> permute(int[] nums) {result.clear();permutation(nums, new ArrayList());return result;}public void permutation(int[] nums, List<Integer> list) {if(list.size() == nums.length) {result.add(list);return;}for(int i = 0; i < nums.length; i++) {if(!list.contains(nums[i])) {List<Integer> subList = new ArrayList<Integer>(list);subList.add(nums[i]);permutation(nums, subList);}}}
}