|
| 1 | +/* |
| 2 | + Problem: Given two numbers, n and k, make all unique combinations of k numbers from 1 to n and in sorted order |
| 3 | +
|
| 4 | + What is combinations? |
| 5 | + - Combinations is selecting items froms a collections without considering order of selection |
| 6 | +
|
| 7 | + Example: |
| 8 | + - We have an apple, a banana, and a jackfruit |
| 9 | + - We have three objects, and need to choose two items, then combinations will be |
| 10 | +
|
| 11 | + 1. Apple & Banana |
| 12 | + 2. Apple & Jackfruit |
| 13 | + 3. Banana & Jackfruit |
| 14 | +
|
| 15 | + To read more about combinations, you can visit the following link: |
| 16 | + - https://betterexplained.com/articles/easy-permutations-and-combinations/ |
| 17 | +
|
| 18 | + Solution: |
| 19 | + - We will be using backtracking to solve this questions |
| 20 | + - Take one element, and make all them combinations for k-1 elements |
| 21 | + - Once we get all combinations of that element, pop it and do same for next element |
| 22 | +*/ |
| 23 | + |
| 24 | +class Combinations { |
| 25 | + constructor (n, k) { |
| 26 | + this.n = n |
| 27 | + this.k = k |
| 28 | + this.combinationArray = [] // will be used for storing current combination |
| 29 | + } |
| 30 | + |
| 31 | + findCombinations (high = this.n, total = this.k, low = 1) { |
| 32 | + if (total === 0) { |
| 33 | + console.log(this.combinationArray) |
| 34 | + return |
| 35 | + } |
| 36 | + for (let i = low; i <= high; i++) { |
| 37 | + this.combinationArray.push(i) |
| 38 | + this.findCombinations(high, total - 1, i + 1) |
| 39 | + this.combinationArray.pop() |
| 40 | + } |
| 41 | + }; |
| 42 | +} |
| 43 | + |
| 44 | +/* |
| 45 | + Driver Code |
| 46 | +
|
| 47 | + Test Case 1: n = 3, k = 2 |
| 48 | + Test Case 2: n = 4, k = 2 |
| 49 | +*/ |
| 50 | + |
| 51 | +console.log('\nFirst Test Case') |
| 52 | +const test1 = new Combinations(3, 2) |
| 53 | +test1.findCombinations() |
| 54 | + |
| 55 | +console.log('\nSecond Test Case') |
| 56 | +const test2 = new Combinations(4, 2) |
| 57 | +test2.findCombinations() |