3 
Print all combinations of a number N, as a sum of positive integers?
They should be unique

例子

3 =
1 2

1 1 1

.

4=
3 1

2 2

1 1 2

1 1 1 1

我已经使用回溯解决了这个问题，但问题是它也给出了重复项，例如 3

我正进入（状态

1 1 2

2 1 1

如何仅获得独特的组合？

非常感谢提前

4

7 回答 7

5

当你创建你的背部时，你总是从最后一个数字开始（第一次你认为 1 作为最后一个数字）（基本上你保持一个排序的解决方案）这就是你始终保持唯一解决方案的方式。

#include <iostream>

const int N = 4;

int sol[N];
int sum = 0;
int nr_of_elements;

void back(int lastElement)
{
    if (sum == N)
    {
        for (int i = 0 ; i < nr_of_elements; i++)
            std :: cout << sol[i] << " ";
        std :: cout << "\n";
        return ;
    }
    for ( int i = lastElement ; i <= N - sum ; i++)
    {
        sum += i;
        sol[nr_of_elements++] = i;
        back(i);
        sum -= i;
        nr_of_elements--;
    }
}

int main ()
{
    back(1);
    return 0;
}
于 2012-06-14T07:34:22.133 回答
3

对于每个数字，您只需要检查大于或等于它的数字。例如：

1 1 1 1
1 1 2
1 2 1 (not this, as the third 1 is less than is precedent 2)
1 3
2 1 1 (not this)
2 2
3 1 (not this)
4
于 2012-06-14T07:41:50.160 回答
2

这是 Ionescu Roberts 答案的 Java 版本：

static Set<List<Integer>> getNums(int last, int target) {

    Set<List<Integer>> toReturn = new HashSet<List<Integer>>();

    if (target == 0) {
        toReturn.add(new ArrayList<Integer>());
        return toReturn;
    }

    for (int i = last; i <= target; i++) {
        for (List<Integer> subSolution : getNums(i, target - i)) {
            List<Integer> seq = new ArrayList<Integer>(subSolution);
            seq.add(i);
            toReturn.add(seq);
        }
    }

    return toReturn;
}
于 2012-06-14T07:29:02.260 回答
2

传递用作参数的最后一个数字。

void rec(int lastUsed)
{
    for (int i = lastUsed; i <= max; i++)
       rec(i);
}
于 2012-06-14T07:33:00.793 回答
0

解决给定问题的回溯的更简洁的实现（请参阅算法设计手册：此处使用的相同模板）。

    #define V(x)  vector<x >    
    typedef V(int) VI; 

    bool  isSolutionReached(VI & input, VI  & partial, int k,int data)  {
     if (k==data) return true;
         return false; 
    }
    void  processSolution(VI & input,VI & partial, int k,int data)   {
      int sum=0,i=0;    
      for(i=0;i<=data;i++)  
    if(partial[i]!=0 ) {
        sum+=i; 
    }
          if(sum == k)  {
    for(i=0;i<=data;i++) 
                      if(partial[i]!=0) cout <<i<<"\t";
     cout <<"\n"; 
       }
    }

    void  constructNext(VI  & input,VI  & candidateVector,int k,int data) {
        candidateVector.push_back(0);
        candidateVector.push_back(1); 
    }
  bool finished=false; 

    void backTrack(VI & inp, VI  &partial,  int k,int data )  {
   VI  candidateVector; 
   int i=0;
    if( isSolutionReached(partial,inp,k,data))  {
    processSolution(inp,partial,k,data);  
}else {
    k=k+1; 
      constructNext(inp,candidateVector,k,data);  
      for(i=0;i<candidateVector.size();i++)  {
          partial[k]=candidateVector[i];  
          backTrack(inp,partial,k,data); 
      }
}
    }


    int main() { 
  int n=5;  //This is x+1 
  VI inp(5,0);  
  VI partial(5,0); 
  backTrack(inp,partial,0,n-1); 
  return 0; 
   }
于 2012-06-14T11:53:32.957 回答
0

这个答案适用于 Java 和 C# 等您可以覆盖等于和哈希码的地方。

最简单的方法是利用现有算法生成 2^N 个可能的组合，但对其进行调整以使用 Set 消除重复项。您的方法将返回一组所有组合并且不包含重复项。现在您需要告诉 Set 如何识别 2 个重复的组合：使用列表，并覆盖 equals 和 hashcode 方法。

您想将组合存储在一个列表中，让我们调用 UniqueList，它环绕 java.util.ArrayList：

class UniqueList {
    ArrayList data = new ArrayList();
    void add(Integer item) {
        data.add(item);
    }

    //more wrapper calls if you want

    @Override
    public boolean equals(UniqueList anotherList) {
        if (data.size() != anotherList.data.size()) return false
        //only need to sort once in each list
        Collections.sort(data); 
        Collections.sort(anotherList.data);
        for (int i = 0; i < data.size(); i++) {
            if (data.get(i) != anotherList.data.get(i)) return false
        }

        return true;
    }

    //optionally override hashcode for performance on hashtable
}

现在在现有的生成算法中，使用

Set<UniqueList<Integer>>

要保存组合集合，它将保证没有重复，因为 Set 将在接受组合之前使用 equals() 方法进行检查。

您可以添加一个布尔标志来指示列表是否已经排序以避免重复排序 - 换句话说，每个列表只需要排序一次，以检查重复。

这种方法显然不是最优的，但是您可以将其插入现有算法中，以最少的代码更改实现 0 重复。

于 2014-02-13T23:32:12.300 回答
0

您可以跟踪先前的变量以确保不重复解决方案。如果当前的缩减因子小于之前的缩减因子，则会导致重复解。简而言之，确保数字按升序排列。这是我的 C++ 代码。

#include <iostream>
#include <vector>

using namespace std;

void printSum(vector<string> &v, int n, int prev, string s) {
    if(n == 1)
        return;
    for(int i = 1; i <= n/2; i++) {
        if(i < prev)
            continue;
        string temp = s + to_string(i) + " ";
        v.push_back(temp + to_string(n - i));
        printSum(v, n - i, i, temp);
    }
}

int main() {
    int n;
    vector<string> v;
    
    cin>>n;
    printSum(v, n, 0, "");
    v.push_back(to_string(n)); //This is to include n in the possible sum as well
    /* Output for n = 4;
       ["1 3", "1 1 2", "1 1 1 1", "2 2", "4"]
    */ 
    
    for(auto s: v)
        cout<<s<<"\n";
    return 0;
}
于 2021-10-23T05:01:57.500 回答