我遇到了一些问题的理解/执行这个问题。基本上，这是自我导向的，并且将AP preciate如果有人能阐明的递归结构光（某种伪code将AP preciated）。

什么我卡上的问题3 - 每一张选票计数搜索

http://see.stanford.edu/materials/icspacs106b/H18- Assign3RecPS.pdf

我尝试理解它是可以产生选举结果的数量没有索引指定块。如果块推压在多数的表决票数，那么它是非常关键的。但我怎么把这种想法变成code？

澄清 这是它们是指，其工作方式，需要被改变，以回答上述问题的热身问题：

 布尔CanMakeSum（矢量＆lt; INT＆GT;＆安培; NUMS，诠释targetSum）{

如果（targetSum == 0）{

    反++;
    COUT＆LT;＆LT; listSubset（partial_solution）＆LT;＆LT; ENDL;

} 其他 {

    的for（int i = 0; I＆LT; nums.size（）;我++）{

        INT元= NUM​​S [I]

        矢量＆lt; INT＆GT;休息= NUM​​S;
        rest.removeAt（ⅰ）;
        partial_solution.add（元）;

        INT newTargetSum = targetSum  - 元;

            如果（CanMakeSum（休息，newTargetSum））{

                返回true;

            }

        INT remove_place = partial_solution.size（） -  1;
        partial_solution.removeAt（remove_place）;

    }
}


如果（计数器大于0）{

    COUT＆LT;＆LT; 存在子集的数量是：＆其中;＆其中;计数器＆LT;＆LT; ENDL;
    返回true;

}

返回false;
}

字符串listSubset（矢量＆lt; INT＆GT;＆安培; partial_solution）{

串溶液=这些总量可达到的总和：;

的for（int i = 0; I＆LT; partial_solution.size（）;我++）{
    解决方案+ =整数到（partial_solution [I]）+;
}

返回的解决方案;

}
 

解决方案

您有一些组的投票块，

 的std ::矢量＆lt; INT＆GT; V = {4,2，7,4}
 

还有一共有17票，其中多数楼（（17 + 1）/ 2）或摆动选举所需的9票。

让我们假设从零索引的集合（这将是一个矢量毕竟），并要找到关键的选票块3（其中有4票）。

首先，建立剩余块的集合：

 的std ::矢量＆lt; INT＆GT; R = {4,2，7}
 

现在发现，收集的 幂 的。这项工作提到了您presumably之前曾在ListSubsets功能;这将是相关的。重新实现轻松使用的std ::设为和一点递归。如果你想使用的std ::矢量完全做到这一点，你所要做的唯一性测试自己。

 无效find_powerset（STD ::设为＆LT;的std ::设为＆LT; INT＆GT;＆GT;＆安培;幂，性病::集＆LT; INT＆GT;初）
{
  powerset.insert（初始）;

  为（自动I = initial.begin（！）; I = initial.end（）;我++）
  {
    的std ::设为＆LT; INT＆GT; new_set（初始）;
    new_set.erase（new_set.find（* I））;
    find_powerset（幂，new_set）;
  }
}
 

您可以调用这个简单的是，

 的std ::设为＆LT;的std ::设为＆LT; INT＆GT;＆GT;幂;
find_powerset（幂，性病::集＆LT; INT＆GT;（r.begin（），r.end（）））;
 

这最终会产生这样的东西（虽然的std ::设为不会让这个顺序的东西，当然）。

  {}
{4}
{2}
{7}
{4,2}
{4,7}
{2,7}
{4,2，7}
 

现在只需加起来的总票数中的每个子集：

  0，4，2，7，6，11，9，13
 

如何将这些投票的结果不已经超过了大多数计数的多，将超过多数计数时，与当前块的投票相结合？您可能会发现，在行使热身B的任务是相关的。

这一步可以用previous一个相结合，通过修改幂上面的函数只返回的子集，其总和落入适当的范围内。这将作为练习留给读者。

总之，答案是仅2， {7} 和 {4,2} 。在所有其他的结果，最终块的投票不会改变任何东西。很简单！

I'm experiencing some issues understanding/executing this problem. Basically, this is self-directed, and would appreciate if someone could shed light on the structure of the recursion (pseudocode of some kind would be appreciated).

What I'm stuck on is Problem 3 - search for "Every Vote Counts."

http://see.stanford.edu/materials/icspacs106b/H18-Assign3RecPS.pdf

My attempt at understanding it is you can generate the number of voting outcomes without the block specified at the index. If the block pushes the number over the majority of votes, then it is critical. But how do I translate this idea into code?

Clarification This is the warm-up problem that they are referring to, which works, that needs to be altered to answer the above problem:

bool CanMakeSum(Vector<int> & nums, int targetSum) {

if (targetSum == 0) { 

    counter++;
    cout << listSubset(partial_solution) << endl;

} else {

    for (int i = 0; i < nums.size(); i++) {

        int element = nums[i];

        Vector<int> rest = nums;
        rest.removeAt(i);
        partial_solution.add(element);

        int newTargetSum = targetSum - element;

            if (CanMakeSum(rest, newTargetSum)) {

                return true;

            }

        int remove_place = partial_solution.size() - 1;
        partial_solution.removeAt(remove_place);

    }
}


if (counter > 0) {

    cout << "The number of subsets that exist are: " << counter << endl;
    return true;

}

return false;
}

string listSubset(Vector<int> &partial_solution) {

string solution = "These total up to the sum: ";

for (int i = 0; i < partial_solution.size(); i++) {
    solution += IntegerToString(partial_solution[i]) + " ";
}

return solution;

}

You have some set of voting blocks,

std::vector<int> v = { 4, 2, 7, 4 }

There's a total of 17 votes, with a majority of floor((17 + 1) / 2) or 9 votes needed to swing the election.

Lets assume the collection is indexed from zero (it will be in a vector after all), and you want to find the critical votes for block 3 (which has 4 votes).

First, build a collection of the remaining blocks:

std::vector<int> r = { 4, 2, 7 }

Now find the powerset of that collection. The exercise makes reference to a 'ListSubsets' function you presumably worked on before; it will be relevant. Reimplementation is easy using std::set and a bit of recursion. If you wanted to do this using std::vector exclusively, you'll have to do uniqueness testing yourself.

void find_powerset(std::set<std::set<int>> &powerset, std::set<int> initial)
{
  powerset.insert(initial);

  for (auto i = initial.begin(); i != initial.end(); i++)
  {
    std::set<int> new_set(initial);
    new_set.erase(new_set.find(*i));
    find_powerset(powerset, new_set);
  }
}

You can invoke this simply enough,

std::set<std::set<int>> powerset;
find_powerset(powerset, std::set<int>(r.begin(), r.end()));

Which will ultimately generate stuff like this (though std::set will not keep things in this order, of course).

{ }
{ 4 }
{ 2 }
{ 7 }
{ 4, 2 }
{ 4, 7 }
{ 2, 7 }
{ 4, 2, 7 }

Now simply add up the total votes in each subset:

0, 4, 2, 7, 6, 11, 9, 13

How many of these voting outcomes which don't already exceed the majority count, will exceed the majority count when combined with the current block's votes? You may find the "warmup B" task in the exercise to be relevant.

This step can be combined with the previous one, by modifying the powerset function above to only return subsets whose sum falls into the appropriate range. This is left as an exercise to the reader.

Anyway, the answer is "just 2", { 7 } and { 4, 2 }. In all other outcomes, the vote of the final block won't change anything. Easy!