子集,组合,全排列

原创
2020/12/28 20:04
阅读数 32

思路分析

回溯算法思路模板:

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

子集题目描述

子集题目解题代码

public class Subsets {

    /**
     * result = []
     * def backtrack(路径, 选择列表):
     *     if 满足结束条件:
     *         result.add(路径)
     *         return
     *     for 选择 in 选择列表:
     *         做选择
     *         backtrack(路径, 选择列表)
     *         撤销选择
     */

    LinkedList<LinkedList<Integer>> solutions = new LinkedList<>();


    public LinkedList<LinkedList<Integer>> subsets(int[] nums) {

        if (nums == null) {
            return null;
        }

        LinkedList<Integer> ls = new LinkedList<>();

        findResluts(nums, 0, ls);

        return solutions;


    }


    private void findResluts(int[] nums, int start, LinkedList<Integer> integers) {

        solutions.add(integers);
        for (int i = start; i < nums.length; i++) {
            integers.add(nums[i]);
            findResluts(nums, i + 1, integers);
            integers.pollLast();
        }
    }

    public static void main(String[] args) {
        new Subsets().subsets(new int[]{1, 2, 3});
    }
}
}

集合题目描述

集合解题代码

class Solution {

    List<List<Integer>> combineSolutions = new ArrayList<List<Integer>>();


    public List<List<Integer>> combine(int n, int k) {

        ArrayList<Integer> ls = new ArrayList<>();

        findCombineResult(1,n,k, ls);

        return combineSolutions;
    }

    private void findCombineResult(int start,int n,int k, ArrayList<Integer> integers){
        if (integers.size() == k){
            combineSolutions.add(new ArrayList<>(integers));
        }
        for (int i = start; i <= n; i++) {
            integers.add(i);
            findCombineResult(i + 1, n,k,integers);
            integers.remove(integers.size() - 1);
        }

    
}

全排列题目描述

全排列解题代码

class Solution {
   
    private List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {

        LinkedList<Integer> tracks = new LinkedList<>();

        goCal(nums,tracks);

        return res;
    }

    public void goCal(int[] nums,LinkedList<Integer> tracks){



        if (nums.length == tracks.size()) {

            res.add(new LinkedList<>(tracks));

            return;
        }

        for (int num :nums){

            if (tracks.contains(num)){
                continue;
            }

            tracks.add(num);

            goCal(nums,tracks);

            tracks.removeLast();

        }

    }



}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部