求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; }
|