0

谢谢@Scotty，@paddy。仅供参考，最佳解决方案是：

void RecSubsets(string soFar, string rest) {
    if (rest == "") {
        cout << soFar << end;
    }
    else {
      RecSubsets(soFar + rest[0], rest.substr(1));
      RecSubsets(soFar, rest.substr(1));
    }
 }

void CanMakeSum(string set) {
    RecSubsets("", set);
 }

我正在编写一个简单的程序，通过将数据分成两组（C（n-1，k-1）和C（n-1，k））并递归调用函数来计算一组中所有可能的组合。下面是我写的：

void RecSubsets(string soFar, string rest) {
    if (rest == "") cout << soFar << end;
    }
    else {
        for (int i = 0; i < rest.length(); i++) {
            string next = soFar + rest[i];
            string remaining = rest.substr(i+1);
            RecSubsets(next, remaining);
        }
    }
}

void CanMakeSum(string set) {
    RecSubsets("", set);
    RecSubsets("", set.substr(1));
}

int main() {    
    string set = "abcd";
    CanMakeSum(set);
    return 0;
}

因此，对于“abcd”的输入字符串，它会分成 2 组（abcd 和 abc），然后通过递归调用函数来打印出组合。在这个逻辑下，输出应该是：abcd, abc, abd, ab, acd, ac, ad, a... 但是，使用上面的程序，输出是 abcd, abd, acd, ad... 我明白了从概念上讲，我想要实现的目标，但很难将其转换为代码。有人可以指出我哪里出错了吗？谢谢

4

2 回答 2

0

这是一个很好的尝试。只有两个小问题：

  1. 您不应该“将数据分成两组 (C(n-1, k-1) & C(n-1, k))”。这就是你的递归函数的用途！

  2. RecSubsets()应该总是打印出来soFar。删除if (rest == "").

例如：

void RecSubsets(string soFar, string rest) {
    // First print out "a" or wherever we are up to
    // This ensures we correctly get "ab" and "ac" without trailing characters etc
    cout << soFar << end;

    // Now print out the other combinations that begin with soFar
    // This part of your algorithm was already correct :)
    for (int i = 0; i < rest.length(); i++) {
        string next = soFar + rest[i];
        string remaining = rest.substr(i+1);
        RecSubsets(next, remaining);
    }
}

void CanMakeSum(string set)
{
    RecSubsets("", set);
    // Don't call it a second time here
}
于 2012-09-07T00:46:07.203 回答
0

您希望在后订购而不是预订购中打印结果。另一个答案几乎是正确的，但是您太轻易地忽略了它。它没有进行排列，因为没有对字符串进行重新排序。

按您需要的顺序输出数据的正确代码是：

void RecSubsets(string soFar, string rest) {
    for (int i = 0; i < rest.length(); i++) {
        string next = soFar + rest[i];
        string remaining = rest.substr(i+1);
        RecSubsets(next, remaining);
    }
    if( soFar.size() > 0 ) cout << soFar << endl;
}

输出：

abcd
abc
abd
ab
acd
ac
ad
a
bcd
bc
bd
b
cd
c
d
bcd
bc
bd
b
cd
c
d
于 2012-09-07T02:55:32.027 回答