46. 全排列


给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

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


思路:
        回溯法,分别将(第一个,第二个...第nums.length-1个)元素和首个元素交换
                    1{2,3,4}
                    2{1,3,4}
                    3{1,2,4}
                    4{1,2,3}
                    递归执行{2,3,4} {1,3,4} {1,2,4} {1,2,3} 的全排序
如图:
   
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        backstack(nums,0,nums.length,res);
        return res;
    }

    private void backstack(int[] nums,int begin,int end, List<List<Integer>> res){

        if(begin==end){
            List<Integer> tem = new ArrayList<Integer>();
            for (int n = 0; n < nums.length; n++) {
                tem.add(nums[n]);
            }
            res.add(tem);
            return;
        }
        for (int i = begin; i <end; i++) {//begin-end 之间的全排列
            swap(nums,i,begin);
            backstack(nums,begin+1,end,res);
            swap(nums,i,begin);

        }
    }

    private  void swap(int[] nums, int x, int y) {
        int a = nums[x];
        nums[x] = nums[y];
        nums[y] = a;
    }
}

  • 作者:低调做个路人 (扫码联系作者)
  • 发表时间:2019-12-03 14:07:34
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 评论