For the past two months I spent many hours solving algorithmic problems. It’s fun, but very time-consuming. I think the majority of time is spent on trying to find accurate solutions and systematic ways for problem solving. I also spent a few weeks (!) grasping data structure fundamentals.
Anyway, this post just describes a technique I came into when reading this book , page 73, on using integers to find all possible subsets from a list of length n. Example Leetcode problem: https://leetcode.com/problems/subsets/description/
The key insights are:
- Every int is binary represented in a machine’s memory as a sequence of 0’s and 1’s
- The range of ints from 0 to 2**n-1, have included all possible combinations of 0’s and 1’s for a list of length n.
- Think about every position’s value (0 or 1) as an indicator whether element at that position appears or not.
- So for every int from 0 to 2 **n -1, we only need to extract all the positions that are 1, to get the combination of list elements this int represents
- With bitwise operators & and shift operator <<, we can easily get whether the i-th element of an int is 1 (turned on) or 0 (turned off). Try X & (1 << i).
- Looping through all positions from 0 to (n-1) we can get all valid bits for this int. We append the corresponding elements to the answer list corresponding to this int.
- Finally, we collect every answer list to a big list and return.
Very smart and interesting strategy. Code snippet here: https://codepad.co/snippet/Tm6Z5ZZP
This strategy can used for other exhaustive search problems that requires looping through all possible combinations of n elements, with exponential time complexity ( 2**n). But the very fast bit manipulation makes it evades the time limit.