【LeetCode】No.78. Subsets -- Java Version

题目链接：https://leetcode.com/problems/subsets/

1. 题目介绍（Subsets）

Given an integer array nums of unique elements, return all possible subsets (the power set).

【Translate】： 给定一个包含多个唯一元素的整数数组，返回所有可能的子集(幂集)。

The solution set must not contain duplicate subsets. Return the solution in any order.

【Translate】： 解决方案集不得包含重复的子集。你可以以任何顺序返回解决方案。

【测试用例】：

【条件约束】：

2. 题解

2.1 双循环

原题解来自于TWiStErRob的Simple iteration (no recursion, no twiddling) + explanation。

他的想法是从一个空子集开始，然后取或不取输入数组中的下一个元素，他通过了listMap的size()巧妙的设置了内层循环的范围，保证了所有情况。下方是输入[1,2,3]的情况：

由于该题对于返回结果的order没有要求，所有这里我省略了原题解中的sort()排序，如果要求了排序，这就需要到了sort()。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> listMap = new ArrayList<>();
      
        listMap.add(new ArrayList<>());
        
        for (int i = 0; i < n; i++){
            for (int j = 0,size = listMap.size(); j < size; j++){
                List<Integer> list = new ArrayList<>(listMap.get(j));
                list.add(nums[i]);
                listMap.add(list);
            }
        }
        
        return listMap;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.2 递归

原题解来自于yetiiiiii的 📌 [Java] Intuition of Approach | Backtracking。

class Solution {
    List<List<Integer>> result;
    public List<List<Integer>> subsets(int[] nums) {
        result = new ArrayList();
        if(nums==null || nums.length==0) return result;
        
        subsets(nums,new ArrayList<Integer>(), 0);
        return result;
    }
    
    private void subsets(int[] nums, ArrayList<Integer> temp, int index) {
        // base condition
        if(index >= nums.length) {
            result.add(new ArrayList<>(temp));
            return;
        }
        
        // main logic
		// case 1 : we pick the element
        temp.add(nums[index]);
        subsets(nums, temp, index+1); // move ahead
        temp.remove(temp.size()-1);
        
		// case 2 : we don't pick the element ( notice, we did not add the current element in our temporary list
        subsets(nums, temp, index+1); // move ahead
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

更多的题解详见 issac3的 A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning)。

3. 参考资料

[1] List＜List＜Integer＞＞初始化方法 | CSDN
[2] power set的定义和理解 | CSDN