Блог пользователя the_pyhulk

All Possible Subsets Of An Array..
Автор the_pyhulk, история, 2 года назад, По-английски

Method 1:- RECURSIVE APPROACH

In this method there are only two basic insights whether to ‘take’ or ‘not take’.

var subsets = function(nums) { let res=[] // the final arr, which we will display let auxArr = [], i=0 // global vars

function recur(nums,i,auxArr){
    if(i==nums.length) { res.push(auxArr); return } //operation of recursion will be upto i=n-1
                               // when it will hit, i==n, it will store the computed arr, in the final arr, and break(return)

    // take it
    recur(nums, i+1, [...auxArr, nums[i] ] )
    // dont take
   recur(nums, i+1, auxArr)

}

recur(nums,i,auxArr) // passing the global variable declared already
return res        // return the final 2d arr

};

                  1 2 3

/ \ 1 [] / \ /. \ 1 2 1 2. [] / \ / \ / \ / \ 123. 12. 13. 1. 23. 2. 3. [].

All the left hand parts are the results of ‘take it’ and right hand are ‘don’t take it’

Method 2:- ITERATIVE APPROACH

var subsets = function(nums) { let res = [[]], appendarr= []

for(let num of nums){
    appendarr = []
    for(let entry of res){
        appendarr.push([...entry, num])
    }

    res.push(...appendarr)
}

return res

};

0 (Empty) : [] 1 (Adding 1 to it) : [] [1] 2 (Adding 2 to it) : [] [1] [2] [1,2] 3 (Adding 3 to it) : [] [1] [2] [1,2] [3] [1,3] [2,3] [1,2,3]

Method 3:- BIT MASKING

var subsets = function(nums) { const result = []; result.push([]); // handling the first case (i=0). for that, an empty arr should be there

let size = nums.length

for(let i = 1; i < (1<<size) ; i++){ // generating for range upto [(2^n)-1] let subset = []; let bitmask=0

while(bitmask<size){
      if(i & (1 << bitmask)){           // if it exists (not zero)
          subset.push( nums[bitmask] );
      }
      bitmask++   
  }
  result.push(subset)

} return result };

Lets Dry Run our code:-

So lets take nums=[1,2,3] we will be searching all elem from 0-> 2^n

so, checking :

i
⬇ while(bitmask<size)

0 [000] [ ]

1 [001] i=1.
i 001 001 001 mask 001 010 100 ---- ---- ---- [001] 000 000

2 [010] i=2.
i 010 010 010 mask 001 010 100 — — --- 000 [010] 000

3 [011] i=3.
i 011 011 011 mask 001 010 100 — — --- [001] [010] 000

4 [100] i=4.
i 100 100 100 mask 001 010 100 — — --- 000 000 [100]

5 [101] i=5.
i 101 101 101 mask 001 010 100 — — --- [001] 000 [100]

6 [110] i=6.
i 110 110 110 mask 001 010 100 — — --- 000 [010] [100]

7 [111] i=7.
i 111 111 111 mask 001 010 100 — — --- [001] [010] [100]

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Great Topic, here are some of my implementations in C++ for the same:

Subsets using backtracking:

Backtrack

Subsets using Bit-mask:

Bit-mask

Note: The variables are all initialized in int format. Also the above methods will generate subsets based on indexes and not actual numbers, Therefore, if a number was repeated in the input array, the subsets will be generated considering the repeated numbers as different from each other. Eg: [1, 2, 2] be the original array, [1, 2] will appear twice in our final collection as the algorithm cannot differentiate between the repeated '2'.

→ Ответить