The original question can be found here.
The question is asking to return all subsets of an integer array, and each element in the array is unique.
Recursion
Normally the question which is asking for all possible solutions are searching. For questions about searching, normally it’s questioning you if you know recursion or not. For questions about serching, it must be permutation and combination problem.
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList();
helper(res, new ArrayList<Integer>(), nums, 0);
return res;
}
private void helper(List<List<Integer>> res,
List<Integer> holder,
int[] nums,
int pos) {
res.add(new ArrayList<Integer>(holder));
for (int i = pos; i < nums.length; i++) {
holder.add(nums[i]);
helper(res, holder, nums, i + 1);
holder.remove(holder.size() - 1);
}
}
}Time complexity: O(2^n) where n is the size of the array.
Space complexity: O(n) because we use a temperory holder array to hold the values.