求1-n之间所有不重复的可能的值的和等于m的组合

求1-n之间所有不重复的可能的值的和等于m的所有组合

思路：

采用二叉树结构，根节点为岗哨，无实际意义，从根节点开始，其左孩子节点表示选中1，有孩子节点表示不选中1，以此类推。

从根节点开始遍历，若此节点的sum< M,则递归调用此节点，若sum>M,则return，若sum=M，则回溯所有的节点。

 

具体代码如下：

 

#include <stdio.h>
#include <malloc.h>
#define M 10
#define N 10
typedef int ElemType;
typedef struct Node
{
    ElemType sum; //到此节点时的所有节点值的和
    ElemType level;//此节点位于第几层
    struct Node *lchild;
    struct Node *rchild;
    struct Node *parent;
}Node,*LinkList;

 

//回溯此节点直到root

void reverseVisit(Node *node)
{
 Node *tmp;
    printf("%d+",node->level);
 tmp = node ->parent;
    while(tmp!=NULL)
    {
  if (tmp->parent != NULL && tmp->parent->lchild == tmp)
   printf("%d+",tmp->level);
  tmp = tmp->parent;
    }
    printf("\n");
}

//本程序的核心

void visitTree(Node *root)
{
    Node *l,*r;
    if(root->sum > M || root->level > N)
        return;
    if(root->sum < M)
    {
         l=(LinkList)malloc(sizeof(Node));
         l->level = root->level+1;
         l->sum=l->level + root->sum;
         l->lchild=NULL;
         l->rchild = NULL;
         l->parent = root;
         r=(LinkList)malloc(sizeof(Node));
         r->level = root->level+1;
         r->sum= root->sum;
         r->lchild=NULL;
         r->rchild = NULL;
         r->parent = root;

         root->lchild = l;
         root->rchild = r;
         visitTree(l);
         visitTree(r);
    }
    if(root->sum==M)
    {
          reverseVisit(root);
    }
}

 

int main(void)
{
   Node *root=(LinkList)malloc(sizeof(Node));
   root->level = 0;
   root->sum=0;
   root->lchild=NULL;
   root->rchild = NULL;
   root->parent = NULL;
   visitTree(root);
   return 0;
}