Using Bitmasking Algorithm to Compute the Combinations of an Arr

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

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:
8 Content Marketing Plugins You Need For Your WordPress Blog
Tips to Make Money from the Comfort of Your Own Home
5 Tips for Protecting Your Freelance Business from Liabilities
5 Easy Ways On How To Build An Authority Website
How to Protect Your WordPress Site From Hackers
Top 10 Relationship Blogs With the Best Pieces of Advice in 2020
How to Construct Binary Search Tree from Preorder Traversal in P
Dynamic Programming Algorithm to Compute the Block Sum in a Matr
Smallest Multiple Algorithm using Bruteforce or GCD/LCM
How many different ways can £2 be made using any number of coins
Share:Facebook Twitter
Comment list
Comment add