Backtracking and dynamic programming

Backtracking a recursive programming technique to solve problems incrementally and remove solutions that fail to satisfy the constraints of the problem.
Backtracking is used to explore all possible solutions.
Below are the simple steps of how backtracking works:

• Start solving the problem with a possible move.
• If the move chosen does not lead to a solution, backtrack and choose another path.
• Continue this process until either solution is found or have explored all possible moves.

Problem:

How the backtracking approach is suitable here :
- Constraints are : 1) index mod nums[index] == 0 or nums[index] mod index == 0
2) same number should not be repeated in a permutation
If solution not meeting these constraints , go with next possible solution that is next number.
- Start with either of the approaches:
a) Start with number 1 and if the solution reaches upto n+1 , then we reached a valid permutation , increment the count by one
b) start with number n and if the solution reaches to 0th number, then we reached a valid permutation, increment the count by one.
note: My observation is that with approach (b) is faster than approach (a).

While using this backtracking approach, there are some repeated partial solutions computed. These partial solutions can be stored by using memoization.

Complexity

• Time complexity:

Its a recursive approach and a function has a loop of 1 to n.
TC is O(k*n) where n is number of elements and k is the number of valid permutations.

• Space complexity:

In either dynamic programming or normal backtracking approach we use an array of n elements.
SC is O(n).

Code:

/* THIS SOLUTION USES BACKTRACKING APPROACH */

/* recursive function to count valid permutations */
int countvalidarrangements (int index, int n, int* used){
    /* index reached a limit  means arrived to a valid permutation, returning 1 count*/
    if (index == 0)
        return 1;
    int cnt = 0;
    /* go over each number 1 to n */
    for (int num = 1; num <=n; num++){
        /* constraints here are:
           num should be used again
           num % index or index % num should be 0 */
        /* used array is to indicate if numbers are already used or not */
        if ((used[num] == 0) && ((index % num == 0) || (num % index ==0)))
        {
            /* set this value so that in next recursions that number will not be used */
            used[num] = 1;
            /* add the count with return values of recursive call */
            cnt += countvalidarrangements(index-1, n, used);
            /* reset used */
            used[num] = 0;
        }
    }
    return cnt;
}

int countArrangementBT(int n) {
    int  used[n+1];
    int ii=0;
    for (ii=0; ii<=n; ii++){
        used[ii] = 0;
    }
    /* calling a backtracking function starting with first index */
    int cnt = countvalidarrangements(n, n, used);
  
    return cnt;
}
struct dp_mem{
    int used_mask;
    int cnt;
};

struct dp_ans{
    struct dp_mem *sols;
    int num_sols;
    int max_sols;
};

/* use the above logic and memoization to avoid repeated computations
   also use the bit mask instead of used array*/
int countvalidarrangements_dp (int index, int n, struct dp_ans* dp, int used_mask){
    /* index reached a limit  means arrived to a valid permutation, returning 1*/
    if (index == 0)
        return 1;
    
    /* go over already calculated solutions */
    for (int ii=0; ii<dp[index].num_sols; ii++){
        if (dp[index].sols[ii].used_mask == used_mask){
            return dp[index].sols[ii].cnt;
        }
    }
    int cnt = 0;
    /* go over each number 1 to n */
    for (int num = 1; num <=n; num++){
        /* constraints here are:
           num should be used again
           num % index or index % num should be 0 */
        /* used array is to indicate if numbers are already used or not */
        if (!(used_mask & (1<<num)) && ((index % num == 0) || (num % index ==0)))
        {
            /* add the count with return values of recursive call */
            cnt += countvalidarrangements_dp(index-1, n, dp, (used_mask | (1<<num)));
        }
    }
    if (dp[index].num_sols < dp[index].max_sols){
        dp[index].sols[dp[index].num_sols].used_mask = used_mask;
        dp[index].sols[dp[index].num_sols++].cnt = cnt;
    }
    return cnt;
}


int countArrangement(int n) {
    struct dp_ans dp[n+1];
    int ii=0;
    for (ii=0; ii<=n; ii++){
        dp[ii].sols = (struct dp_mem *)malloc(30*sizeof(struct dp_mem));
        dp[ii].num_sols = 0;
        dp[ii].max_sols = 30;
    }
    /* calling a backtracking function starting with first index */
    int cnt = countvalidarrangements_dp(n, n, dp, 0);
    for (ii=0; ii<=n; ii++){
        free(dp[ii].sols);
    }
   
    return cnt;
}