Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
Run through a set of example cases:
HAPPY CASE
Input: [5, 3, 9]
Output: [[],[5],[3],[3,5],[9],[5,9],[3,9],[3,5,9]]
Input: [1, 3, 4, 10, 9]
Output: [[],[1],[3],[1,3],[4],[1,4],[3,4],[1,3,4],[10],[1,10],[3,10],[1,3,10],[4,10],[1,4,10],[3,4,10],[1,3,4,10],[9],[1,9],[3,9],[1,3,9],[4,9],[1,4,9],[3,4,9],[1,3,4,9],[9,10],[1,9,10],[3,9,10],[1,3,9,10],[4,9,10],[1,4,9,10],[3,4,9,10],[1,3,4,9,10]]
EDGE CASE
Input: [10]
Output: [[],[10]]
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Loop over the length of combination, rather than the candidate numbers, and generate all combinations for a given length with the help of backtracking technique.
1) when the nums equals zero, it means there is zero elements to work, append them in the result and return.
2) choose not to include nums[0] in the subsets and explore all the subsets of nums[1:]
3) choose to include nums[0] in the subsets and explore all the subsets of nums[1:]⚠️ Common Mistakes
This problem is different than the rest of the usual backtracking practice problems in the sense that in this problem, we dont have a separate base case that tells us when to stop with the recursion. We keep looping until we run out of indexes. This will then mark the end of our recursion.
Implement the code to solve the algorithm.
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
# use dictionary to store combinations
self.res = {():True}
self.helper((), nums)
return self.res.keys()
def helper(self, val, data):
# if we have tried all numbers in the subset - finish the recursion
if not data: return
# this loop helps us to create all possible combinations for numbers in data
for i in range(len(data)):
# if current index less then previous - means that we already has such
# subset but in another order. In that way we avoid sorting for checking
# if we already have this subset in the self.res
if val and val[-1] > data[i]:
continue
new_val = val + (data[i], )
# if we do not have that subset in the store - adding it
# and tuple as a keys because it a great improving of speed instead of using list
if new_val not in self.res:
self.res[new_val] = True
# run the same code for the new value and options for iteration.
self.helper(new_val, data[:i]+data[i+1:])
class Solution {
// function to perform backtracking.
static void Function(List<List<Integer>> list , List<Integer> permutation , int[] nums , int start)
{
// add new subset
list.add(new ArrayList<>(permutation));
for(int i=start;i<nums.length;i++)
{
permutation.add(nums[i]);
// start from next index psition.
Function(list,permutation,nums,i+1);
// delete the last elment added.
permutation.remove(permutation.size()-1);
}
}
public List<List<Integer>> subsets(int[] nums) {
// add all the possible subsets generated
List<List<Integer>> list = new ArrayList<>();
List<Integer> permutation = new ArrayList<>();
Function(list,permutation,nums,0);
return list;
}
}Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
