Permutation 2019/01/05

import java.util.*;

class Main {
    public static void main(String[] args) {
        System.out.println(findPermutation(new int[]{1,2,3}));
    }
    
    public static List<List<Integer>> findPermutation(int[] input) {
        List<List<Integer>> result = new ArrayList<>();
        if (input == null || input.length == 0) return new ArrayList<>();

        dfsWithBacktrack(input, result, new ArrayList<>());
        return result;
    }

    private static void dfsWithBacktrack(int[] input, List<List<Integer>> result, List<Integer> level) {
        //Base case
        if (level.size() == input.length) result.add(new ArrayList<>(level));
 
        for (int neighbor : input) {
            if (level.contains(neighbor)) continue;
            //Backtracking
            level.add(neighbor);
            dfsWithBacktrack(input, result, level);
            level.remove(level.size() - 1);
        }
    }

}