package LeetCode;

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

public class LeetCode47 {
    //https://leetcode-cn.com/problems/permutations/description/
    // 
    private ArrayList res;
    private boolean[] used;

    public List permute(int[] nums) {

        res = new ArrayList();
        if (nums == null || nums.length == 0)
            return res;

        used = new boolean[nums.length];
        LinkedList p = new LinkedList();
        generatePermutation(nums, 0, p);

        return res;
    }

    // pindex-1
    // index, index
    private void generatePermutation(int[] nums, int index, LinkedList p) {

        if (index == nums.length) {
            res.add((List) p.clone());
            return;
        }

        for (int i = 0; i < nums.length; i++)
            if (!used[i]) {
                used[i] = true;
                p.addLast(nums[i]);
                generatePermutation(nums, index + 1, p);

                // 
                p.removeLast();
                used[i] = false;
            }

        return;
    }

    private static void printList(List list) {
        for (Integer e : list)
            System.out.print(e + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        int[] nums = {1, 2, 3};
        List res = (new LeetCode47()).permute(nums);
        for (List list : res)
            printList(list);
    }

}