Top 100
Subsets
- Problem
- LC 78
- File
- top100_LC78Subsets.java
- Path
- pkg5leetcode/top100/top100_LC78Subsets.java
- Package
- pkg5leetcode.top100
- Command
- java pkg5leetcode/top100/top100_LC78Subsets.java
- Approach
- Backtrack include/exclude each element.
- Complexity
- Time O(2^n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.top100;2 3/*4 * Subsets | LC 785 * APPROACH: Backtrack include/exclude each element.6 * COMPLEXITY: Time O(2^n), Space O(n)7 */8import java.util.*;9 10public class top100_LC78Subsets {11 static List<List<Integer>> subsets(int[] nums) {12 List<List<Integer>> res = new ArrayList<>();13 backtrack(nums, 0, new ArrayList<>(), res);14 return res;15 }16 17 static void backtrack(int[] nums, int i, List<Integer> cur, List<List<Integer>> res) {18 res.add(new ArrayList<>(cur));19 for (int j = i; j < nums.length; j++) {20 cur.add(nums[j]);21 backtrack(nums, j + 1, cur, res);22 cur.remove(cur.size() - 1);23 }24 }25 26 public static void main(String[] args) {27 check(subsets(new int[]{1, 2, 3}).size() == 8, "case1");28 check(subsets(new int[]{0}).size() == 2, "case2");29 System.out.println("all tests passed");30 }31 32 static void check(boolean cond, String name) {33 if (!cond) throw new AssertionError("FAILED: " + name);34 System.out.println(" PASS " + name);35 }36}