Subsets of backtracking algorithms for combat series

This is the 27th day of my participation in Gwen Challenge

This article specifically selects two algorithm questions for finding subsets, one is an array without repeating elements, and the other is an array with repeating elements, both of which are medium difficulty algorithm questions. It is a classic example of backtracking algorithm application. Let’s try to solve it using backtracking.

Example ⅰ

78. The subset

You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

Example 1:

Input: nums = [1,2,3]

Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Example 2:

Input: nums = [0]

Output: [[], [0]]

Tip:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All elements in NUMS are different

Links: leetcode-cn.com/problems/su…

Code Practice ⅰ

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) {
            backTracking(nums, res, i, 0.new Stack<>());
        }
        return res;
    }

    public void backTracking(int[] nums, List<List<Integer>> res, int length, int index, Stack<Integer> subset) {
        if (subset.size() == length) {
            ArrayList<Integer> list = new ArrayList<>();
            list.addAll(subset);
            res.add(list);
            return;
        }

        for (int i = index; i < nums.length; i++) {
            subset.add(nums[i]);
            backTracking(nums, res, length, i + 1, subset); subset.pop(); }}}Copy the code

Example ⅱ

90. The subset II

Given an array of integers, nums, which may contain repeating elements, return all possible subsets (power sets) of that array.

The solution set cannot contain duplicate subsets. Returns a solution set in which subsets can be arranged in any order.

Example 1:

Input: nums = [1,2,2]

Output: [[], [1], [1, 2],,2,2 [1], [2], [2]]

Example 2:

Input: nums = [0]

Output: [[], [0]]

Tip:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

Links: leetcode-cn.com/problems/su…

Code Combat ii

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();
        boolean[] used=new boolean[nums.length];
        backTracking(nums,res,used,0.new LinkedList<>());
        return res;
    }

    public void backTracking(int[] nums,List<List<Integer>> res,boolean[] used,int index, LinkedList<Integer> path){
        res.add(new LinkedList<>(path));
        if(index>=nums.length){
            return;
        }
        for(inti=index; i<nums.length; i++){if(i>0&&! used[i-1]&&nums[i]==nums[i-1]) {continue;
            }
            used[i]=true;
            path.add(nums[i]);
            backTracking(nums,res,used,i+1,path);
            used[i]=false; path.removeLast(); }}}Copy the code