c++ - 将启发式应用于递归回溯

搜索其他问题——也有类似的问题，但没有一个解决这个特殊的启发式问题。
我有一个问题的工作代码，它要求将一个向量转换成某个函数，确定该向量中的任何值是否和给定的目标值相加，然后返回它是否是（布尔值）。这很简单。
我必须使用提供的回溯启发式来创建这个函数（如下所示），它在原则上工作正常。我必须确保我的函数不会生成以前生成的组合（例如，ABC与BAC相同）。如何防止代码执行此操作？我无法更改进入函数的参数（因此函数原型必须保持如下），但是包装器或帮助器函数是可以的。
以下是启发：

  bool Solve(configuration conf) {
       if (no more choices) // BASE CASE
         return (conf is goal state);

  for (all available choices) {

        try one choice c;
        // recursively solve after making choice

  ok = Solve(conf with choice c made);
   if (ok) return true;
   else unmake choice c;

   }
   return false; // tried all choices, no soln found
  }

我的代码：

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

if (nums.isEmpty()) {

    cout << "you've reached the target sum" << endl;
    return true;

} else {

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

        element = nums[i];
        Vector<int> rest = nums;
        cout << "list the subset: " << listSubset(rest) << endl;
        rest.removeAt(i);

        // try one
        int new_target_sum = targetSum - element;

        CanMakeSum(rest, new_target_sum);

            if (new_target_sum == 0) {
                return true;

            } else {

            new_target_sum = targetSum + element;

        }
    }
}

return false;
}


string listSubset(Vector<int> &partial_solution) {

string solution = " ";

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

return solution;

}

最佳答案

在选择元素时可以引入排序。例如，在选择ith element之后，不能选择索引小于i的任何元素。代码中所需的更改是，在选择ith element之后，需要将索引0到i中的所有元素移除。