Combinations

Definition

Definition

The Combinations Algorithm generates all possible combinations of elements from a given set without considering the order of elements

Explanation

The algorithm accepts a set of elements and a desired combination size. It employs recursion to systematically construct combinations by selecting elements iteratively. At each iteration, it evaluates whether to include the current element. This process persists until the combination achieves the target size, upon which it is appended to the result set. This cycle continues for all elements in the set until all possible combinations are exhausted

Guidance

• Start with an empty combination and an empty result set
• Iterate through each element in the given set
  • for each element, decide whether to include it in the current combination or not
    • if including the element, add it to the current combination and recursively call the algorithm with a reduced target size and remaining elements
    • if not including the element, skip it and recursively call the algorithm with the same target size and remaining elements
    • repeat steps until the target size is reached
    • add the generated combination to the result set
• Repeat for all elements in the set
• Return the result set containing all possible combinations

Tips

• utilize recursion to simplify the implementation
• keep track of the current combination and remaining elements during recursion
• use backtracking to efficiently explore all possible combinations

Practice

Practice

generateCombinations(set, targetSize, currentCombination, index, results)
  if size of currentCombination is equal to targetSize
    add currentCombination to results
    return
  end if

  if index is equal to size of set
    return
  end if

  // Include the current element
  add set[index] to currentCombination
  generateCombinations(set, targetSize, currentCombination, index + 1, results)

  // Exclude the current element
  remove set[index] from currentCombination
  generateCombinations(set, targetSize, currentCombination, index + 1, results)

end function

// Example usage:
results = []
set = [1, 2, 3, 4]
targetSize = 2
generateCombinations(set, targetSize, [], 0, results)
print results

Solution

package main

func combineWithoutRepetitions(comboOptions []int, comboLength int) [][]int {
	if comboLength == 1 {
		result := make([][]int, len(comboOptions))
		for i, v := range comboOptions {
			result[i] = []int{v}
		}
		return result
	}

	var combos [][]int

	for optionIndex, currentOption := range comboOptions {
		smallerCombos := combineWithoutRepetitions(comboOptions[optionIndex+1:], comboLength-1)

		for _, smallerCombo := range smallerCombos {
			combos = append(combos, append([]int{currentOption}, smallerCombo...))
		}
	}

	return combos
}

func combineWithRepetitions(comboOptions []int, comboLength int) [][]int {
	if comboLength == 1 {
		result := make([][]int, len(comboOptions))
		for i, v := range comboOptions {
			result[i] = []int{v}
		}
		return result
	}

	var combos [][]int

	for optionIndex, currentOption := range comboOptions {
		smallerCombos := combineWithRepetitions(comboOptions[optionIndex:], comboLength-1)

		for _, smallerCombo := range smallerCombos {
			combos = append(combos, append([]int{currentOption}, smallerCombo...))
		}
	}

	return combos
}

import java.util.ArrayList;
import java.util.List;

public class Main {

  public static List<List<Integer>> combineWithoutRepetitions(List<Integer> comboOptions, int comboLength) {
    List<List<Integer>> combos = new ArrayList<>();
    if (comboLength == 1) {
      for (Integer comboOption : comboOptions) {
        List<Integer> list = new ArrayList<>();
        list.add(comboOption);
        combos.add(list);
      }
    } else {
      for (int i = 0; i <= comboOptions.size() - comboLength; i++) {
        int currentOption = comboOptions.get(i);
        List<List<Integer>> smallerCombos = combineWithoutRepetitions(comboOptions.subList(i + 1, comboOptions.size()), comboLength - 1);
        for (List<Integer> smallerCombo : smallerCombos) {
          List<Integer> newList = new ArrayList<>();
          newList.add(currentOption);
          newList.addAll(smallerCombo);
          combos.add(newList);
        }
      }
    }
    return combos;
  }

  public static List<List<Integer>> combineWithRepetitions(List<Integer> comboOptions, int comboLength) {
    List<List<Integer>> combos = new ArrayList<>();
    if (comboLength == 1) {
      for (Integer comboOption : comboOptions) {
        List<Integer> list = new ArrayList<>();
        list.add(comboOption);
        combos.add(list);
      }
    } else {
      for (int i = 0; i < comboOptions.size(); i++) {
        int currentOption = comboOptions.get(i);
        List<List<Integer>> smallerCombos = combineWithRepetitions(comboOptions.subList(i, comboOptions.size()), comboLength - 1);
        for (List<Integer> smallerCombo : smallerCombos) {
          List<Integer> newList = new ArrayList<>();
          newList.add(currentOption);
          newList.addAll(smallerCombo);
          combos.add(newList);
        }
      }
    }
    return combos;
  }
}

function combineWithoutRepetitions(comboOptions, comboLength) {
  if (comboLength === 1) {
    return comboOptions.map((comboOption) => [comboOption]);
  }

  const combos = [];

  comboOptions.forEach((currentOption, optionIndex) => {
    const smallerCombos = combineWithoutRepetitions(
      comboOptions.slice(optionIndex + 1),
      comboLength - 1,
    );

    smallerCombos.forEach((smallerCombo) => {
      combos.push([currentOption].concat(smallerCombo));
    });
  });

  return combos;
}

function combineWithRepetitions(comboOptions, comboLength) {
  if (comboLength === 1) {
    return comboOptions.map((comboOption) => [comboOption]);
  }

  const combos = [];

  comboOptions.forEach((currentOption, optionIndex) => {
    const smallerCombos = combineWithRepetitions(
      comboOptions.slice(optionIndex),
      comboLength - 1,
    );

    smallerCombos.forEach((smallerCombo) => {
      combos.push([currentOption].concat(smallerCombo));
    });
  });

  return combos;
}

fun combineWithoutRepetitions(comboOptions: List<Int>, comboLength: Int): List<List<Int>> {
    val combos = mutableListOf<List<Int>>()
    if (comboLength == 1) {
        for (comboOption in comboOptions) {
            combos.add(listOf(comboOption))
        }
    } else {
        for (i in 0..comboOptions.size - comboLength) {
            val currentOption = comboOptions[i]
            val smallerCombos = combineWithoutRepetitions(comboOptions.subList(i + 1, comboOptions.size), comboLength - 1)
            for (smallerCombo in smallerCombos) {
                combos.add(listOf(currentOption) + smallerCombo)
            }
        }
    }
    return combos
}

fun combineWithRepetitions(comboOptions: List<Int>, comboLength: Int): List<List<Int>> {
    val combos = mutableListOf<List<Int>>()
    if (comboLength == 1) {
        for (comboOption in comboOptions) {
            combos.add(listOf(comboOption))
        }
    } else {
        for (i in comboOptions.indices) {
            val currentOption = comboOptions[i]
            val smallerCombos = combineWithRepetitions(comboOptions.subList(i, comboOptions.size), comboLength - 1)
            for (smallerCombo in smallerCombos) {
                combos.add(listOf(currentOption) + smallerCombo)
            }
        }
    }
    return combos
}

def combine_without_repetitions(combo_options, combo_length):
    combos = []
    if combo_length == 1:
        for combo_option in combo_options:
            combos.append([combo_option])
    else:
        for i in range(len(combo_options) - combo_length + 1):
            current_option = combo_options[i]
            smaller_combos = combine_without_repetitions(combo_options[i + 1:], combo_length - 1)
            for smaller_combo in smaller_combos:
                combos.append([current_option] + smaller_combo)
    return combos


def combine_with_repetitions(combo_options, combo_length):
    combos = []
    if combo_length == 1:
        for combo_option in combo_options:
            combos.append([combo_option])
    else:
        for i in range(len(combo_options)):
            current_option = combo_options[i]
            smaller_combos = combine_with_repetitions(combo_options[i:], combo_length - 1)
            for smaller_combo in smaller_combos:
                combos.append([current_option] + smaller_combo)
    return combos

fn combine_without_repetitions(combo_options: &[i32], combo_length: usize) -> Vec<Vec<i32>> {
    let mut combos = Vec::new();
    if combo_length == 1 {
        for &combo_option in combo_options {
            combos.push(vec![combo_option]);
        }
    } else {
        for i in 0..=combo_options.len() - combo_length {
            let current_option = combo_options[i];
            let smaller_combos = combine_without_repetitions(&combo_options[i + 1..], combo_length - 1);
            for smaller_combo in smaller_combos {
                let mut new_combo = vec![current_option];
                new_combo.extend_from_slice(&smaller_combo);
                combos.push(new_combo);
            }
        }
    }
    combos
}

fn combine_with_repetitions(combo_options: &[i32], combo_length: usize) -> Vec<Vec<i32>> {
    let mut combos = Vec::new();
    if combo_length == 1 {
        for &combo_option in combo_options {
            combos.push(vec![combo_option]);
        }
    } else {
        for i in 0..combo_options.len() {
            let current_option = combo_options[i];
            let smaller_combos = combine_with_repetitions(&combo_options[i..], combo_length - 1);
            for smaller_combo in smaller_combos {
                let mut new_combo = vec![current_option];
                new_combo.extend_from_slice(&smaller_combo);
                combos.push(new_combo);
            }
        }
    }
    combos
}

function combineWithoutRepetitions(
  comboOptions: number[],
  comboLength: number,
): number[][] {
  const combos: number[][] = [];
  if (comboLength === 1) {
    for (const comboOption of comboOptions) {
      combos.push([comboOption]);
    }
  } else {
    for (let i = 0; i <= comboOptions.length - comboLength; i++) {
      const currentOption = comboOptions[i];
      const smallerCombos = combineWithoutRepetitions(
        comboOptions.slice(i + 1),
        comboLength - 1,
      );
      for (const smallerCombo of smallerCombos) {
        combos.push([currentOption, ...smallerCombo]);
      }
    }
  }
  return combos;
}

function combineWithRepetitions(
  comboOptions: number[],
  comboLength: number,
): number[][] {
  const combos: number[][] = [];
  if (comboLength === 1) {
    for (const comboOption of comboOptions) {
      combos.push([comboOption]);
    }
  } else {
    for (let i = 0; i < comboOptions.length; i++) {
      const currentOption = comboOptions[i];
      const smallerCombos = combineWithRepetitions(
        comboOptions.slice(i),
        comboLength - 1,
      );
      for (const smallerCombo of smallerCombos) {
        combos.push([currentOption, ...smallerCombo]);
      }
    }
  }
  return combos;
}