Given a data set, n elements are selected from the set and the possible combinations of elements are asked.

Combination characteristics: internal elements are disordered, that is, [1,2,3] and [3,2,1] are the same combination

Common methods for combination are: recursive method, conversion method

The recursive method

If you have n elements (it doesn’t matter whether they are repeated or not), how many ways can you pick m elements at a time?

For example, if there are five balls [1,2,3,4,5], three of which can be taken at A time and put into a. how many ways can there be?

You can follow the following steps to remove and place

  1. Step 1: You can put 1 into A, so that leaves 2, 3, 4, 5

    • Step 2: You can put 2 into A, which leaves 3, 4, and 5

      • Step 3: Put the 3 into A, then complete A combination
      • Step 3: Put 4 into A, then complete A combination
      • Step 3: Put 5 into A, then complete A combination

    • Step 2: You can put 3 into A, so that leaves 4 and 5

      • Step 3: Put 4 into A, then complete A combination
      • Step 3: Put 5 into A, then complete A combination

    • Step 2: You can put 4 into A, so you still have 5 left

      • Step 3: Put 5 into A, then complete A combination

  2. Step 1: You can put 2 into A, so you’re left with 3, 4, 5

    • Step 2: You can put 3 into A, so that leaves 4 and 5

      • Step 3: You can put 4 into A to complete A combination
      • Step 3: You can put 5 into A to complete A combination

    .

According to the above analysis, A is A container. We can take out one of the remaining balls and put it into A container every time. For example:

  • 1 of 1, 2, 3, 4 and 5 can be taken out and put into container A. At this time, the remaining ball is 2, 3, 4 and 5, and container A is not full.
  • You can take no. 2 out of the remaining balls and put it into the container, where the remaining balls are 3, 4, 5 and the container is not full;
  • Finally, we take no. 3 out of the remaining balls and put it into the container. At this time, the remaining balls are 4 and 5 and the container is full, which means that a combination is satisfied

The following ideas can be drawn from the above analysis:

  1. For a bunch of balls, where each ball can be taken out, you can recycle the rest so that it’s possible to put all the balls into the container
  2. Since the combination is disordered, placing the balls in sequence does not affect the result. For example, putting 1 first and then 2 is the same as putting 2 first and then 1. In order to avoid double calculation, the positions of the balls are not changed when placing the balls, and they are placed from front to back
  3. When the container is full, a combination is completed

Code by idea

function fullCombination(nums: number[], pick: number) :number[] []{
  const ans: number[] [] = [];/ / the result
  recursion([], 0);
  return ans;

  function recursion(container: number[], startInd: number) :void {
    // Container represents the elements contained in the current container. When the container is full, a combination is completed
    if (container.length === pick) {
      ans.push(container);
      return;
    }

    // It is impossible to reach the number of picks
    if(startInd + pick > nums.length)return;

    for (let i = startInd; i < nums.length; i++) {
      const c = container.slice();
      c.push(nums[ i ]);
      recursion(c, i + 1); }}}Copy the code

Conversion method

Continuing the example above, putting [1,2,3,4,5] into the container, we use 0,1 to describe whether a ball is selected, with 0 indicating that it is not selected and 1 indicating that it is selected. For example, if all five elements are not selected and all of them are [0,0,0,0,0,0], [1,1,1,1], if only three elements are selected, the three right-most elements are [0,0,1,1,1], and the three left-most elements are [1,1,1,0,0]. Then all combinations can be described as the conversion process from [1,1,1,0,0] ==> [0,0,1,1,1]

Conversion method

Assuming that the starting position is,1,1,0,0 [1], then the next choice should be,1,0,1,0 [1], continue to the next choice should be,1,0,0,1 [1]… Until,0,1,1,1 [0]

According to the above rules:

  1. [I,j]; [I,j]; [I,j]; [I,j]; For example [1,0,0,1,1] the first 1,0 index is represented as [0,1]
  2. Reverse 1,0, that is, swap I,j; After the swap, it is [0,1,0,1,1]
  3. For j< index <= nums.length-1, all 1 is moved to the right of array j, 0 is moved to the far left; When 1< index <=4, i.e. in the case of index>j, there are two ones, then move the two ones to the right of j [0,1,1,1,0]
  4. Until I can’t find 1,0
// Move one step
function stepNext(picks: number[]) :boolean {
  const first10Index = findFirst10(picks); // Step 1 find the first 1,0 from left to right

  if (first10Index === -1) return false; // Step 4 If it cannot be found, the combined enumeration ends

  swap(picks, first10Index, first10Index - 1); // Step 2 Swap I,j
  moveToLeft(picks, first10Index + 1, picks.length - 1); // Step 3 Move 1
  return true;
}

function findFirst10(nums: number[]) :number {
  let prev = nums[ nums.length - 1 ];
  let first10Index = nums.length - 1;

  for (let i = nums.length - 2; i >= 0; i--) {
    if (prev === 0 && nums[ i ] === 1) break;
    first10Index = i;
    prev = nums[ i ];
  }
  return first10Index === 0 ? -1 : first10Index;
}

function moveToLeft(nums: number[], left: number, right: number) {
  let i = left, j = left;
  while (j <= right) {
    if (nums[ j ] === 1) { swap(nums, i, j); i++; } j++; }}function swap(nums: number[], i: number, j: number) :void {
  const k = nums[ i ];
  nums[ i ] = nums[ j ];
  nums[ j ] = k;
}
Copy the code

The index transformation

The above only describes the combination of subscripts corresponding to the number, such as [1,1,1,0,0], which cannot represent the final number, so the index needs to be converted to a number

function transform(originNums: number[], picks: number[]): number[] {
  const v = [];
  for (let i = 0; i < picks.length; i++) {
    if (picks[ i ] === 1) {
      v.push(originNums[ i ]);
    }
  }
  return v;
}
Copy the code

The specific implementation

function fullCombination(nums: number[], pick: number) :number[] []{
  const ans: number[] [] = [];const start = new Array(nums.length).fill(0);
  for (let i = 0; i < pick; i++){
    start[ i ] = 1;
  }

  do {
    ans.push(transform(nums, start));
  } while (stepNext(start))

  return ans;
}
Copy the code