LeetCode46. 全排列

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

class Solution {
        private List<List<Integer>> ans;

        private int[][] nums;

        private List<Integer> tmp;

        public List<List<Integer>> permute(int[] nums) {
            tmp = new ArrayList<>();
            ans = new ArrayList<>();
            this.nums = new int[nums.length][];
            for (int i = 0; i < nums.length; i++) {
                this.nums[i] = new int[2];
                this.nums[i][0] = nums[i];
                this.nums[i][1] = 0;
            }
            dfs();
            return this.ans;
        }

        public void dfs() {
            if (tmp.size() == nums.length) {
                List<Integer> list = new ArrayList<>();
                list.addAll(tmp);
                ans.add(list);
                return;
            }

            for (int i = 0; i < nums.length; i++) {
                if (nums[i][1] == 0) {
                    nums[i][1] = 1;
                    tmp.add(nums[i][0]);
                    dfs();
                    tmp.remove(tmp.size() - 1);
                    nums[i][1] = 0;
                }
            }
        }
    }