Understanding Subsets of an Array problem

This is a popular question in the coding interviews and if you have a good grasp of the solution you can tackle a lot of variations of this problem.

So the pattern of question matches something like you are given a number N or an array of N numbers and you have to return all the possible subsets of this array or the subset of a given size K.

This looks like a straightforward question and indeed it is but in an interview-setup the permutations and recursion doesn't always go so well. :)

So let me share the diagram that has helped me to understand. Truly with recursion if you can imagine the solution in a tree diagram it really helps in writing the solution.

That’s me on top-right truly happy with sharing this art.

So to begin with we will start with an empty array. At each level, we will take care of both the available options i.e. include the number at current index/level in the array and also not include.

Then after that we will increment the index to point to the next index. We will keep doing this till the base case is reached which in this case will be when the index is equal to the length of original array.

And that’s it. Whenever the base case is reached we will store the current list to our final result which is a list of lists.

// Without duplicates
public static List<List<String>> findSubsets(String[] arr) {
        List<List<String>> result = new ArrayList<>();

        recursive(result, new ArrayList<String>(), 0, arr);

        return result;
    }

private static void recursive(List<List<String>> result, ArrayList<String> r, int idx, String[] arr) {
        if (idx == arr.length) {
            result.add(r);
            return;
        }

        recursive(result, new ArrayList<>(r), idx + 1, arr);
        r.add(arr[idx]);
        recursive(result, new ArrayList<>(r), idx + 1, arr);
    }

The runtime complexity can be deduced from the above logic as well. Since at each level we are branching the solution in 2 directions(include and exclude) and if there are N numbers in the array, the overall runtime of this solution is 2^N.

Hope this would be helpful. :)