c++ - 给定数字列表有多少种方法可以得到 21？如何获得所有可能的数字组合？

Question

好吧，所以我必须解决这个问题，用户给出一个 7 或 k 数字的列表，我必须告诉有多少种方法可以得到 21 或 n 使用这些数字的加法和减法。 我必须使用所有数字。
例如，用户给出数字:(1 3 4 5 9 1 7)。我可以将所有这些数字放入一个长度为 7 的数组中，并计算使用这些数字的总和和/或减数得到 21 的次数:1 +/- 3 +/- 4 +/- 5 +/- 9 +/- 1 +/- 7。

这个问题的代码已经做好了:

count-twenty-one(int* dig, int n, int pos, int sum, int res) {
   if (pos==n) {
       if(sum==21)
         return res++;
   }
   count-twenty-one(dig, n, pos+1, sum+dig[pos], res)
   count-twenty-one(dig, n, pos+1, sum-dig[pos], res)
}

如您所见，这会生成一个 DFS(深度优先搜索)来查找有多少种方法可以得到 21。现在，实际的问题是如何知道有多少种方法可以使用 给定数字的组合，我必须再次使用所有这些数字。例如，用户给出数字:

(0 0 0 0 2 1 0)。我无法使用 0 + 0 - 0 + 0 + 2 + 1 + 0 得到 21。但是如果我附加 2 和 1 并将它与其他 0 相加/相加，我可以得到 21。0 + 0 + 0 - 0 + 21 -0 = 21 假设用户现在给出 (2 3 9 8 5 0 7)。有了这个，我可以得到像 23 98 5 7 这样的数字，并尝试看看有多少种方法可以得到所需的数字。但是话又说回来，我可以拥有 239 8 507。

所以我想主要的问题是获取从 (1 到 k) 的所有可能的数字组合 -K 是数字列表的长度 - 然后使用 count-twenty-one 在所有这些。我该怎么做呢？我正在使用 C++ 和数组。

编辑:

这个问题可以通过获取给定数组的所有可能分区，然后将所有这些分区放入 count-twenty-one 来解决。有什么想法吗？

编辑 2:这些数字是“有序的”，这意味着 (2 3 9 8 5 0 7) 我无法形成像 705 8 93 2

这样的组合

Answer 1

对于蛮力方法，以下可能会有所帮助:https://ideone.com/jAVRDk

void print(const std::vector<int>& digits,
           const std::vector<int>& seps,
           const std::vector<std::string>& s) {
    std::cout << digits[0];
    for (std::size_t i = 0; i != seps.size(); ++i) {
        std::cout << s[seps[i]] << digits[i + 1] ;
    }
    std::cout << std::endl;
}

bool next(std::vector<int>& seps)
{
    for (auto it = seps.rbegin(); it != seps.rend(); ++it) {
        if (++*it == 3) {
            *it = 0;
        } else {
            return true;
        }
    }
    return false;
}

void foo(std::vector<int> digits)
{
    const std::vector<std::string> s = {"", " + ", " - "};
    std::sort(digits.begin(), digits.end());

    do {
        std::vector<int> seps(digits.size() - 1, 0);

        do {
            print(digits, seps, s);
        } while (next(seps));
    } while (std::next_permutation(digits.begin(), digits.end()));

}