Bitmap approach


  • 0

    We can look at this problem in a different way. Its equivalent to generate list of integers with N bits in which K bits set as 1. To generate such integers, we can iterate through each bit position, either filled as 1 or filled as 0 and go to the next bit position. And stop the iteration when the number of "1" bits counts to K. We can extend the same logic for generating combinations of K integers from a list of N integers.

            for (int i = index; i < len; i++)
            {
                curResult.push_back(i + 1);
                genCombinations(n, i + 1, results, curResult, k - 1);
                curResult.pop_back();
            }
        }
    

    The above iteration does the same thing. Include current element and go to the next element. Then, exclude the current element and go to the next element. It generates all the combinations!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.