“This is my 28th day of participating in the First Challenge 2022. For details: First Challenge 2022.”

Given an array of integers, no two elements in the array are the same. Requires that all possible subsets of the array be returned. Subsets cannot contain duplicate subsets and can be returned in any order.

Their thinking

The solution is to build a recursion tree, recurse again and again, and finally take the values of all the leaf nodes as the result, requiring that all the returned values are not repeated. Therefore, the problem uses the VISIT array to mark the elements visited each time. Let’s look at LeetCode 39, which also requires that the results should not be repeated when calculating the number of combinations. Here, a starting point is set for each recursion, and the solution starts from this starting point in recursion. What they want to get are the eligible leaves and the intermediate results.

This is a little bit like the previous two problems, but the ultimate goal is to find all the nodes of the tree. We can imagine that every time we build a tree, we add nodes to a new container, and the sum of the container is our answer. And since we want elements not to be duplicated, we can set a starting point for the array, which ensures that the final result is unique, as follows:

ArrayList<List<Integer>> res = new ArrayList<>(); / / the total container
    ArrayList<Integer> temp = new ArrayList<>(); // Intermediate container
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    public void dfs(int[] nums, int start){
        res.add(new ArrayList<>(temp));
        for(inti=start; i<nums.length; i++){ temp.add(nums[i]); dfs(nums, i+1);
            temp.remove(temp.size()-1); }}Copy the code

The above code is a classic backtracking. The backtracking termination condition is to judge whether the current starting point is greater than the length of the array. If so, the backtracking will not continue.

Idea 2

Go through the number group from front to back, and when encountering a number in the array, combine the number with all the existing subsets to form a new subset, so that when the array is traversed, the subset is also calculated, the code is as follows:

public List<List<Integer>> subsets2(int[] nums) {
        ArrayList<List<Integer>> res2 = new ArrayList<>();
        res2.add(new ArrayList<>());
        for(int i=0; i<nums.length; i++){int size = res2.size();
            for(int j=0; j<size; j++){ ArrayList<Integer> temp2 =newArrayList<>(res2.get(j)); temp2.add(nums[i]); res2.add(temp2); }}return res2;
    }
Copy the code

The time complexity of the above method is O(N)O(N)O(N) O(N), and the space complexity is O(1)O(1)O(1) O(1).