import java.util.ArrayList;
import java.util.List;

public class Permutations {

    public List<List<Integer>> permutation(int nums[]) {
        List<List<Integer>> answer = new ArrayList<>();
        backtrack(answer, new ArrayList<>(), nums);
        return answer;
    }

    public void backtrack(List<List<Integer>> answer,  List<Integer> tempList, int [] nums) {

        if(tempList.size() == nums.length){
            answer.add(new ArrayList<>(tempList));
        } else{
            for(int i = 0; i < nums.length; i++){
                if(tempList.contains(nums[i])) {
                    continue; // element already exists, skip
                }
                tempList.add(nums[i]);
                backtrack(answer, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

    public static void main(String args[]) {
        Permutations p = new Permutations();
        int nums[] = {1,2,3};
        System.out.println(p.permutation(nums));
    }
}