美文网首页
每天一题LeetCode【第33天】

每天一题LeetCode【第33天】

作者: 草稿纸反面 | 来源:发表于2017-03-31 10:11 被阅读78次

    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);
                }
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:每天一题LeetCode【第33天】

          本文链接:https://www.haomeiwen.com/subject/yqimottx.html