Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
1 2 3 4 5 6 7 8 9 10
| [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
|
Backtracking solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| public class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, 0); return list; } private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){ list.add(new ArrayList<>(tempList)); for(int i = start; i < nums.length; i++){ tempList.add(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.remove(tempList.size() - 1); } } }
|
Bit solution
code and explanation here
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public List<List<Integer>> subsets(int[] S) { Arrays.sort(S); int totalNumber = 1 << S.length; List<List<Integer>> collection = new ArrayList<List<Integer>>(totalNumber); for (int i=0; i<totalNumber; i++) { List<Integer> set = new LinkedList<Integer>(); for (int j=0; j<S.length; j++) { if ((i & (1<<j)) != 0) { set.add(S[j]); } } collection.add(set); } return collection; }
|