[LeetCode] Permutations

Problem:

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

Solution:

套用Subsets的模版，此处与Subsets不同的地方是只有当当前的path中的元素个数＝num的元素个数的时候，才将path加入到result中（代码红色标注的地方）。此外，由于生成排列的序列时需要检查某元素是否已经在当前的path中，使用了一个visited数组。由于题目默认given collection中没有重复元素，所以另一种方法是直接用path.contans(num[i])来检查。

Java Code:

public class Solution {//test cases:
    //[]
    //null
    //[1,2,3]
    //[1]
    //[1,2,..,100]
    //[1,2,2] -- 不需要考虑
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) {
            return result;
        }
        permuteHelper(num, new ArrayList<Integer>(), result, new boolean[num.length]);
        return result;
    }
    
    private void permuteHelper(int[] num, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result, boolean[] selected) {
        if (path.size() == num.length) {
            result.add(new ArrayList<Integer>(path));
            return;
        }
        
        for (int i = 0; i < num.length; i++) {
            if (selected[i] == true) {//或者path.contains(num[i]) == true
                continue;
            }
            path.add(num[i]);
            selected[i] = true;
            permuteHelper(num, path, result, selected);
            selected[i] = false;
            path.remove(path.size() - 1);
        }
     }
}