Using Bitmasking Algorithm to Compute the Combinations of an Arr

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

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:
What You Need if You Want to Be a Freelancer
Best Ways to Maximize the Speed ​​& Performance of Your Word
Essential Google Chrome Extensions For SEO
10 Inspiring Home Improvement Blogs
How to Get More Comments For Your Blog Posts
Gmail Hacks and Tips for Bloggers
6 Handy Tools That Can Convert Your Website Into An App
7 Common Email List Building Mistakes
How to Do Email Marketing in 2020: A Beginner’s Guide
5 Music Blogs That Are Rocking It And How To Get Your Own Band F
Share:Facebook Twitter
Comment list
Comment add