• 算法通关村-----回溯模板如何解决排列组合问题


    组合总和

    问题描述

    给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 对于给定的输入,保证和为 target 的不同组合数少于 150 个。详见leetcode39

    问题分析

    我们可以从candidates[0]开始,不断选取candidates[0],直至target-candidates[0]<=0,如果等于0,则我们得到一个满足条件的组合,否则回退一步,去掉一个candidates[0],添加一个candidates[1],如此不断进行下去,满足局部枚举➕递归+放下前任,我门可以使用回溯模板来解决。

    代码实现

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> numList = new ArrayList<>();
        List<List<Integer>> resultList = new ArrayList();
        combinationSum(candidates,target,0,numList,resultList);
        return resultList;
    }
    
    public void combinationSum(int[] candidates, int target,int index,List<Integer> numList,List<List<Integer>> resultList){
        if(target<0){
            return;
        }
        if(target==0){
            resultList.add(new ArrayList<>(numList));
            return;
        }
        for(int i=index;i<candidates.length;i++){
            numList.add(candidates[i]);
            combinationSum(candidates,target-candidates[i],i,numList,resultList);
            numList.remove(numList.size()-1);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    全排列

    问题描述

    给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

    问题分析

    排列与组合类似,只是重复元素可以按照不同顺序成为不同的排列,我们不再是按顺序的取,而是定义一个used数组判断给定数组的元素是否被使用。当我们的排列结果中的元素与给定数组个数相同时,即得到一个排列,添加到结果数组中。

    代码实现

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> ans = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        permute(res,ans,used,nums);
        return res;
    }
    public void permute(List<List<Integer>> res,LinkedList<Integer> ans,boolean[] used,int[] nums){
        if(ans.size()==nums.length){
            res.add(new ArrayList<>(ans));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            used[i] = true;
            ans.add(nums[i]);
            permute(res,ans,used,nums);
            ans.removeLast();
            used[i] = false;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
  • 相关阅读:
    java程序jar包xjar加密及破解解密
    部署了HTTPS以后重新验证证书如何取消301跳转
    操作系统内存管理
    Android 性能优化如何深入学习:启动、内存、崩溃优化一个都不能少
    【Django-DRF】多年md笔记第5篇:Django-DRF的Request、Response和视图详解
    甘氨胆酸(Cholylglycine)小麦麦清白蛋白纳米粒|叶酸偶联牛血清白蛋白负载卡铂和紫杉醇靶向纳米粒
    长胜证券:黄金“狂飙”,饰品克价破600元,期货价格创十余年新高
    java网络通信
    探索GitHub上的两个革命性开源项目
    Body Glove 与 Yeti Out 推出复古街头时尚系列
  • 原文地址:https://blog.csdn.net/m0_45362454/article/details/132904204