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

similar idea to combinations, but since each element can be added in all positions, we need to use a used array to track whether the element is used in that position, if used do not enter recursion again.

public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        if (num==null||num.length==0) {
            return results;
        }

        permute(results, new ArrayList<Integer>(), num, new boolean[num.length]);

        return results;
    }

    public void permute(List<List<Integer>> results, List<Integer> result, int[] num, boolean[] used) {
        if (result.size()==num.length) {
            results.add(new ArrayList<Integer>(result));
            return;
        }

        for (int i=0; i<num.length; i++) {
            if(!used[i]) {
                result.add(num[i]);
                used[i]=true;
                permute(results, result, num, used);
                used[i]=false;
                result.remove(result.size()-1);
            }
        }
    }

Iterative solution:

The idea is like for [1,2,3], we first insert 1 to the result -> [1], then insert 2 before or after 1 -> [1,2], [2,1], then insert 3 in different positions of the result to generate -> [3,1,2], [1,3,2], [1,2,3], [3,2,1], [2,3,1], [2,1,3].

public List<List<Integer>> permuteIter(int[] num) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        if (num == null || num.length == 0) {
            return results;
        }

        List<Integer> result = new ArrayList<Integer>();
        result.add(num[0]);
        results.add(result);
        for (int i = 1; i < num.length; i++) {
            List<List<Integer>> newRes = new ArrayList<List<Integer>>();
            for (int j = 0; j < results.size(); j++) {
                List<Integer> cur = results.get(j);
                for (int k = 0; k < cur.size() + 1; k++) {
                    List<Integer> item = new ArrayList<Integer>(cur);
                    item.add(k, num[i]);
                    newRes.add(item);
                }
            }
            results = newRes;
        }
        return results;
    }