Using Bitmasking Algorithm to Compute the Combinations of an Arr

  • Time:2020-09-07 12:13:31
  • Class:Weblog
  • Read:25

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Combination Algorithm using Bitmasking

The combination can also be done in Recursive backtracking. However, it can also be implemented using the Bitmasking algorithm.

The idea is to bruteforce all possible configurations (of bitmasks) in O(2^N) where N is the length of the given input set. Then once the configuration has k bit sets, we output the corresponding configuration.

The following is the Python combination implementation using bitmasking.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        for b in (range(1 << n)):
            if bin(b).count('1') == k:
                cur = []
                for i in range(n):
                    if (b & (1 << i)) > 0:
                        cur.append(i + 1)
                ans.append(cur)
        return ans
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        for b in (range(1 << n)):
            if bin(b).count('1') == k:
                cur = []
                for i in range(n):
                    if (b & (1 << i)) > 0:
                        cur.append(i + 1)
                ans.append(cur)
        return ans

and with slight changes – reversing the bit searching – still works

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        for b in reversed(range(1 << n)):
            if bin(b).count('1') == k:
                cur = []
                for i in range(n):
                    if (b & (1 << (n - i - 1))) > 0:
                        cur.append(i + 1)
                ans.append(cur)
        return ans
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        for b in reversed(range(1 << n)):
            if bin(b).count('1') == k:
                cur = []
                for i in range(n):
                    if (b & (1 << (n - i - 1))) > 0:
                        cur.append(i + 1)
                ans.append(cur)
        return ans

The recursive algorithm in C++: Recursive Combination Algorithm Implementation in C++.

Also, another interesting read: combination

–EOF (The Ultimate Computing & Technology Blog) —

Recommend:
The Difference Between Java Map’s compute, computeIfAbsent
How to Fix a Slow/Incorrect Clock on Windows?
How to Put Current Running Program in Background without Being T
How to Break a Palindrome String by Replacing a Character?
How to Make a Safe Online Community for Your Business?
Tips to Find the Best Website Hosting Service
Classic, But Effective Online Marketing Strategies
Binary Search Algorithm to Find the Smallest Divisor Given a Thr
How to Create a Travel Blog Post That Makes Your Audience Fly
8 Best WordPress Membership Plugins
Share:Facebook Twitter
Comment list
Comment add