leetcode 46 Solution

代码解析

package com.demo.s46;

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

/**
 * 全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 */
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        //参数结果定义
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        //排列结果
        List<Integer> numbers = new ArrayList<Integer>();
        for (int n : nums) {
            //初始数组列表
            numbers.add(n);
        }
        //回溯 填空， 从 0 开始 填写  numbers.size() 个数字，结果写到 ret
        backtrack(numbers, ret, numbers.size(), 0);

        return ret;

    }

    /**
     * 回溯
     */
    public void backtrack(List<Integer> output, List<List<Integer>> res, int n, int try1) {
        //填完n个数后
        if (try1 == n) {
            //记录到res
            res.add(new ArrayList<Integer>(output));
        }
        for(int i = try1; i< n; i++) {
            //将i填写到try1位置
            Collections.swap(output, i, try1);
            //将i填写到try1 + 1位置
            backtrack(output, res, n, try1 + 1);
            //还原tray1位置的值，从i+1位置开始重新试填
            Collections.swap(output, try1, i);
        }
    }
}