每天一题LeetCode【第33天】

T46. Permutations【Medium】

题目

给出不同的数字的集合，返回所有可能的排列组合。

例如，
[1,2,3] 有如下的排列组合：

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路

这题比较明显是要用到递归，只要会递归，思路就是正常小孩子就知道的思路：

排列组合（1 2 3）
= 1 + 排列组合（2 3）∪ 2 + 排列组合（1 3）∪ 3 + 排列组合（1 2）
排列组合（2 3）
= 2 + 排列组合（3）∪ 3 + 排列组合（2）
= 23 ∪ 32 

可以看出在数字只有一个的时候到了递归的终点

然后看代码就好了~

代码

代码取自 Top Solution，稍作注释

 public class Solution {
     public List<List<Integer>> permute(int[] nums) {
         //建立要返回的数据形式
        List<List<Integer>> list = new ArrayList<List<Integer>>();
         //开始递归
        backtrack(list, new ArrayList<Integer>(), nums);
        return list;
    }

    //主要算法:递归
     public void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums){
        if(tempList.size() == nums.length){
            //若所有元素都用到了则加到 ArrayList 里面
            list.add(new ArrayList<Integer>(tempList));
        } else{
            for(int i = 0; i < nums.length; i++){
                //如果已经有了这个元素,则跳过这次循环
                if(tempList.contains(nums[i])) continue;
                //下面三步一起看,用到了递归
                tempList.add(nums[i]);
                backtrack(list, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}