algorithm - 如何使用 + 或 - 操作从数字列表中获取数字

Question

在我的问题中，我们得到了一个数字和数字列表，我们应该使用操作 + 或 - 从给定的数字列表中获取第一个数字

例如：-1 是目标数字 1 2 3 5 是给出的数字以获得 -1 解决方案应该是 -1+2+3-5 = -1 或 -1-2-3+5 = -1

目标数字的限制是 -180 到 +180，数字列表的限制是 2 到 20

要找到解决方案，应该使用哪种算法？如果我想使用生成所有可能性，它会有效吗？这个问题的任何二进制解决方案是什么？

谢谢你的帮助

Answer 1

可能变体的数量是2^20; 0让我们生成从到的所有数字2^N。这些数字的二进制表示将是 00000（20 个零）、000...01,0000.10、...、1111（20 个）。想象一下，每个零是负数，一个是正数。

    int target = -1;
    int[] numbers = new int[20];
    Arrays.fill(numbers, 0);

    numbers[0] = 1;
    numbers[1] = 2;
    numbers[2] = 3;
    numbers[3] = 5;
    for(int i=0;i<(1<<20);i++) //masks from 00...00 to 11...11 (from --...--- to ++...+++)
    {
        int sum=0;
        for(int bit=0;bit<20;bit++)
        {
            if(((1<<bit)&i)>0)
            {
                sum+=numbers[bit];
            }
            else
            {
                sum-=numbers[bit];
            }
        }
        if(sum==target)
        {
            System.out.print(target+" = ");
            for(int bit=0;bit<20;bit++)
            {
            if(((1<<bit)&i)>0)
            {
                System.out.print("+"+numbers[bit]);
            }
            else
            {
                System.out.print("-"+numbers[bit]);
            }
            }
            break;
        }
    }

输出：-1 = -1+2+3-5-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0