首页 > 代码库 > [leetcode] Permutations

[leetcode] Permutations

Given a collection of 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], and[3,2,1].

https://oj.leetcode.com/problems/permutations/

思路:生成permutation,这题假设没有重复元素,递归求解,每一次在cur位置填元素,添之前判断钙元素是否已经用过,没用过继续下去,指导cur==n。

public class Solution {	public ArrayList<ArrayList<Integer>> permute(int[] num) {		if (num == null)			return null;		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();		if (num.length == 0)			return res;		int[] permSeq = new int[num.length];		perm(num.length, 0, num, permSeq, res);		return res;	}	private void perm(int n, int cur, int[] num, int[] perm,			ArrayList<ArrayList<Integer>> res) {		if (cur == n) {			ArrayList<Integer> tmp = new ArrayList<Integer>();			for (int i = 0; i < perm.length; i++) {				tmp.add(perm[i]);			}			res.add(tmp);		} else {			int i;			for (i = 0; i < num.length; i++) {				int j;				boolean ok = true;				for (j = cur - 1; j >= 0; j--) {					if (perm[j] == num[i])						ok = false;				}				if (ok) {					perm[cur] = num[i];					perm(n, cur + 1, num, perm, res);				}			}		}	}	public static void main(String[] args) {		System.out.println(new Solution().permute(new int[] { 1, 2, 3,4 }));	}}