如何从给定uint数组中选出相加等于指定值的元素并返回所用元素

解决方案 #

你给出的数组所有元素均为不重复的2的整数次幂，任意正整数的二进制表示唯一，因此你要找的组合等价于n的二进制表示中所有值为1的位对应的2的幂次值，用位运算可以非常高效地完成匹配：

• 核心判断逻辑：对数组中每个元素v，只要n & v == v成立，说明v是组成n的元素之一

代码示例（C#） #

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        uint[] values = new uint[]
        {
            1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
        };
        uint n = 96;
        List<uint> result = new List<uint>();
        
        foreach (uint v in values)
        {
            if ((n & v) == v)
            {
                result.Add(v);
            }
        }
        
        // 输出结果：32、64
        Console.WriteLine(string.Join("、", result));
    }
}

扩展说明 #

如果你的实际业务场景中数组元素不是2的幂次，且仍然保证只有唯一解，可以用回溯法遍历所有可能的子集求和匹配，不过时间复杂度会升高到O(2^k)，k为数组长度，使用前需要确认数组长度不会过大。

内容的提问来源于stack exchange，提问作者UnknownSoldier