I want to find all the decompositions of a number using only odd numbers and up to N numbers max.

For example for the number 7 and N = 3, I can only get 1 1 5, 1 3 3, 7. I can't get 1 1 1 1 3 because it's greater then N.

They hint us to use backtracking.

I strated writing the code and I am stuck. If someone can explian to me how to solve this problem it will be great.

int T(int n, int k)
{
    if (k == 0) 
    {
        return;
    }

    int arr[N];
    int f;
    for (f = 0; f < N; f  )
    {
        arr[f] = 0;
    }
    int sum = 0;
    int j = 1;
    int i = 1;
    int c = 0;

    while (j < k) {
        sum = sum   i;
        arr[c] = i;
        
        if (sum == n)
        {
            for (f = 0; f < N; f  )
            {
                if (arr[f] != 0)
                {
                    printf("%d ", arr[f]);
                }
            }
            printf("\n");
        }
        else if (sum > n)
        {
            arr[c] = 0;
            sum = sum - i;
            i = i - 2;
        }
        else 
        {
            i = i   2;
            j  ;
            c  ;
        }
    }
    T(n, k - 1);
}

CodePudding user response：

Please compile with warnings (-Wall) and fix all of them (-Werror helps make sure you do this). I didn't build your code, but int T(int n, int k) says it returns an int, yet the function code is void.

With backtracking, you can't print at each node because the current node in the graph might not actually lead to a solution. It's premature to commit anything to the result set until you actually reach it.

It's best not to print in functions that perform logical tasks anyway, but it can make the coding easier while developing the logic so I'll stick wiith it.

The backtracking suggestion is a good one. Here's the logic:

The "found result" base case is when n == 0 && k >= 0, if you're decrementing n and k and using them to represent the remaining value to reach the goal and the number of choices left. If you're incrementing variables to count up to n and k, that's fine too, in which case the base case is current_total == n && taken_so_far <= k.

Next, the "failure" base case is k < 0 || n < 0 because we've either overshot n or run out of numbers to take.

After that, the recursive case is, in English, "try taking each number up to n, recursing on the possibility that each number might be part of the solution". Per your spec, we don't accept any sequence of descending numbers which prunes the recursion tree a bit.

Here's the code; again, returning a result is an exercise. I'm using a k-sized array to store potential results, then dumping it to stdout only when a result was found.

#include <stdio.h>
#include <stdlib.h>

void odd_decomposition_search(
    int n, const int k, int taken_length, int *taken
) {
    if (n == 0 && taken_length <= k && taken_length > 0) {
        for (int i = 0; i < taken_length - 1; i  ) {
            printf("%d ", taken[i]);
        }

        printf("%d\n", taken[taken_length-1]);
    }
    else if (n > 0 && taken_length < k) {
        int i = taken_length ? taken[taken_length-1] : 1;

        for (; i <= n; i  = 2) {
            taken[taken_length] = i;
            odd_decomposition_search(n - i, k, taken_length   1, taken);
        }
    }
}

void odd_decomposition(const int n, const int k) {
    if (n <= 0 || k <= 0) {
        return;
    }

    int taken[k];
    odd_decomposition_search(n, k, 0, taken);
}

int main() {
    int n = 7;
    int k = 3;
    odd_decomposition(n, k);
    return 0;
}

If you're having trouble understanding the call stack, here's a visualizer you can run in the browser:

Show code snippet

const oddDecomp = (n, k, taken=[]) => {
  console.log("  ".repeat(taken.length), `[${taken}]`);

  if (n === 0 && taken.length <= k && taken.length) {
    console.log("  ".repeat(taken.length), "-> found result:", taken.join(" "));
  }
  else if (n > 0 && taken.length < k) {
    for (let i = taken.length ? taken[taken.length-1] : 1; i <= n; i  = 2) {
      taken.push(i);
      oddDecomp(n - i, k, taken);
      taken.pop(i);
    }
  }
};

oddDecomp(7, 3);

<iframe name="sif1" sandbox="allow-forms allow-modals allow-scripts" frameborder="0"></iframe>