preface

Just a freshman, the first record is as follows 😁

A, the title

Second, the idea of solving the problem

1. Investigation direction

This is a very simple problem to understand, splitting up the natural numbers, but it’s very difficult to solve with a simple loop. So we thought of DFS deep search (depth first search) to solve the problem. This question is a typical introduction to DFS, and can lead to many variations.

2. Depth first search

Introduction to the

Depth First Search (DFS) : An algorithm used to traverse or Search a tree or graph. Traverse the nodes of the tree along the depth of the tree, searching for branches of the tree as deep as possible. When all the edges of node V have been explored or the node does not satisfy the search conditions, the search will go back to the starting node of the edge where node V is found. The process repeats until all nodes are accessed. It is a blind search, the worst case algorithm time complexity is O(! N).

Not so much as a picture:My DFS template (deep search backtracking) search(I){for(all operators){if (condition true) output; Else search (I +1); Backtrace}}}

3. The problem solving

Positive solution (ascending + no weight)

#include<stdio.h>

int a[100];
int n;
void print(int j)// Output data
{
    for(int i=0; i<=j; i++) {if(i==0) printf("%d",a[i]);
   else  printf("+%d",a[i]);
       }
       printf("\n");
}
void search(int sum,int j ,int s)/ / DFS deep search
{
  for(int i=s; i<=n; i++)// Start from the STH, I =s is guaranteed to be in ascending order
{sum+=i;  
      if(sum>n) return;
      if(sum==n) {a[j]=i; print(j);return; } a[j]=i; search(sum,j+1,i);
        sum-=i;/ / back
  }
}
int main()
{
    while(scanf("%d",&n))// Continuous input
    {
        search(0.0.1);
    }
    return 0;
}

Copy the code

Run a screenshotWe’re going to use the backtracking technique here, sum -= I, and in the search, don’t pay too much attention to the details, the macro analysis function the overall function.

What controls the ascending order? We can start with for(int I =s; i<=n; For (int I =1; int I =1; int I =1; i<=n; I++), without the s variableWe can draw it.

(Deduplicate + ascending)

#include<stdio.h>
int book[100];
int a[100];
int n;
void print(int j)
{
    for(int i=0; i<=j; i++) {if(i==0) printf("%d",a[i]);
   else  printf("+%d",a[i]);
       }
       printf("\n");
}
void search(int sum,int j,int s)
{
  for(int i=s; i<=n; i++)if(book[i]==0){sum+=i;
      if(sum>n) return;
      if(sum==n) {a[j]=i; print(j);return; } a[j]=i; book[i]=1;
      search(sum,j+1,i);

      book[i]=0;
        sum-=i;
  }
}
int main()
{
    while(scanf("%d",&n))
    {
        search(0.0.1);
    }
    return 0;
}

Copy the code

The results forHere, we further use the function of backtracking, using book [] to establish a judgment array to judge whether each number has been taken, if yes, then mark 1 in the record array A [], until finally go to the end of the branch when the return level of backtracking is 0 once, and so on, we can know whether the number has been taken.

conclusion

Using not only deep searching but also backtracking techniques in this problem is a good exercise for beginners like me. Please give me more advice