Permutations

1package pkg5leetcode.top100;2 3/*4 * Permutations | LC 465 * APPROACH: Backtrack swap elements to generate all orderings.6 * COMPLEXITY: Time O(n*n!), Space O(n)7 */8import java.util.*;9 10public class top100_LC46Permutations {11    static List<List<Integer>> permute(int[] nums) {12        List<List<Integer>> res = new ArrayList<>();13        backtrack(nums, 0, res);14        return res;15    }16 17    static void backtrack(int[] nums, int start, List<List<Integer>> res) {18        if (start == nums.length) {19            res.add(Arrays.stream(nums).boxed().collect(java.util.stream.Collectors.toList()));20            return;21        }22        for (int i = start; i < nums.length; i++) {23            swap(nums, start, i);24            backtrack(nums, start + 1, res);25            swap(nums, start, i);26        }27    }28 29    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }30 31    public static void main(String[] args) {32        check(permute(new int[]{1, 2, 3}).size() == 6, "case1");33        check(permute(new int[]{0, 1}).size() == 2, "case2");34        System.out.println("all tests passed");35    }36 37    static void check(boolean cond, String name) {38        if (!cond) throw new AssertionError("FAILED: " + name);39        System.out.println("  PASS " + name);40    }41}