聊聊一个面试中经常出现的算法题：组合运算及其实际应用例子

1
2
3
1,2
1,3
2,3
1,2,3

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[] numbers = { 1, 2, 3, 4 };

        List<List<int>> combinations = GenerateCombinations(numbers);

        foreach (var combination in combinations)
        {
            Console.WriteLine(string.Join(", ", combination));
        }
    }

    static List<List<int>> GenerateCombinations(int[] numbers)
    {
        List<List<int>> result = new List<List<int>>();

        for (int i = 1; i <= numbers.Length; i++)
        {
            GenerateCombinationsUtil(numbers, i, 0, new List<int>(), result);
        }

        return result;
    }

    static void GenerateCombinationsUtil(int[] numbers, int k, int start, List<int> currentCombination, List<List<int>> result)
    {
        if (k == 0)
        {
            result.Add(new List<int>(currentCombination));
            return;
        }

        for (int i = start; i < numbers.Length; i++)
        {
            currentCombination.Add(numbers[i]);
            GenerateCombinationsUtil(numbers, k - 1, i + 1, currentCombination, result);
            currentCombination.RemoveAt(currentCombination.Count - 1);
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int[] numbers = { 1, 2, 3, 4 };
        int k = 2; // 选择的元素数量

        List<List<int>> combinations = GenerateCombinations(numbers, k);

        foreach (var combination in combinations)
        {
            Console.WriteLine(string.Join(", ", combination));
        }
    }

    static List<List<int>> GenerateCombinations(int[] numbers, int k)
    {
        List<List<int>> result = new List<List<int>>();
        List<int> currentCombination = new List<int>();

        GenerateCombinationsHelper(numbers, k, 0, 0, currentCombination, result);

        return result;
    }

    static void GenerateCombinationsHelper(int[] numbers, int k, int start, int currentSize, List<int> currentCombination, List<List<int>> result)
    {
        if (currentSize == k)
        {
            result.Add(new List<int>(currentCombination));
            return;
        }

        for (int i = start; i < numbers.Length; i++)
        {
            currentCombination.Add(numbers[i]);
            GenerateCombinationsHelper(numbers, k, i + 1, currentSize + 1, currentCombination, result);
            currentCombination.RemoveAt(currentCombination.Count - 1);
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
    // 创建集合
        List<Item> itemsList = new List<Item>
    {
      new Item { Number = 1, Amount = 100 },
      new Item { Number = 2, Amount = 200 },
      new Item { Number = 3, Amount = 300 }
    };
    
    // 进行组合
    List<List<Item>> combinations = GenerateCombinations(itemsList);

    // 对组合结果进行运算
    StringBuilder sb = new StringBuilder(1024);
    foreach (var combination in combinations)
    {
      for (var i = 0; i < combination.Count; i++)
      {
        var item = combination[i];
        sb.Append(item.Number);
        if (i < combination.Count - 1)
        {
          sb.Append(" + ");
        }
      }
      var cash = combination.Sum(x => x.Amount);
      sb.AppendLine($" = {cash}");
    }
    
    // 打印结果
    Console.WriteLine(sb.ToString());
    }

    static List<List<Item>> GenerateCombinations(List<Item> numbers)
  {
    List<List<Item>> result = new List<List<Item>>();

    // 从 2 个元素开始进行组合
    for (int i=2; i <= numbers.Count; i++)
    {
      GenerateCombinationsHelper(numbers, i, 0, new List<Item>(), result);
    }

    return result;
  }

    static GenerateCombinationsHelper(List<Item> numbers, int k, int start, List<Item> currentCombination, List<List<Item>> result)
  {
    if (k == 0)
    {
      result.Add(new List<Item>(currentCombination));
      return;
    }

    for (int i = start; i < numbers.Count; i++)
    {
      currentCombination.Add(numbers[i]);
      GenerateCombinationsHelper(numbers, k - 1, i + 1, currentCombination, result);
      currentCombination.RemoveAt(currentCombination.Count - 1);
    }
  }
}

// 定义集合元素类
class Item
{
  // 编号
    public int Number { get; set; }
  
  // 金额
    public decimal Amount { get; set; }
}