p46

发表于 | 分类于 |

LeetCode p46 Permutations 题解

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.解题思路:

见代码，递归。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ansList = new ArrayList<List<Integer>>();
		boolean[] visit=new boolean[nums.length];
		List<Integer> list=new ArrayList<Integer>();
		dfs(ansList, nums, visit, new int[nums.length],0);
		return ansList;

	}
	public void dfs(List<List<Integer>> ansList,int[] nums,boolean[] visit, int[] cur,int count)
	{
		int len= nums.length;
		if (len==count)
		{
			List<Integer> cIntegers=new ArrayList<Integer>();
			for (int i:cur)
			{
				cIntegers.add(i);
				//System.out.println(i);
			}
			//System.out.println("-------------");
			ansList.add(cIntegers);
			return;
		}
		for (int i=0;i<len;i++)
		{
			int a=nums[i];
			if (visit[i])
			{
				continue;
			}
			else {
				visit[i]=true;
				cur[count]=a;
				count++;
				dfs(ansList, nums, visit, cur,count);
				count--;
				visit[i]=false;
			}
		}
	}
}

4.一些总结：