All combinations of elements satisfying given constraints


Given a positive number N, find all combinations of 2*N elements such that every element from 1 to N appears exactly twice and distance between its two appearances is exactly equal to value of the element.

 
For example,


Input:  N = 3
Output:
3 1 2 1 3 2
2 3 1 2 1 3

Input:  N = 4
Output:
4 1 3 1 2 4 3 2
2 3 4 2 1 3 1 4

Input:  N = 7
Output:
1 7 1 2 5 6 2 3 4 7 5 3 6 4
5 1 7 1 6 2 5 4 2 3 7 6 4 3
4 1 7 1 6 4 2 5 3 2 7 6 3 5


Total 52 configurations possible

Note that no combination of elements is possible for some values of N like 2, 5, 6, etc.

 
 

We can use backtracking to solve this problem. The idea is to try all possible combinations for the first element and recursively explore remaining elements to check if they will lead to the solution or not. If current configuration doesn’t result in solution, we backtrack. Note that an element k can be placed at position i and (i+k+1) in the output array where i >= 0 and (i + k + 1) < 2*N.

C++

Java

Download   Run Code

Output:

1 7 1 2 5 6 2 3 4 7 5 3 6 4
1 7 1 2 6 4 2 5 3 7 4 6 3 5
1 6 1 7 2 4 5 2 6 3 4 7 5 3
1 5 1 6 7 2 4 5 2 3 6 4 7 3
1 4 1 5 6 7 4 2 3 5 2 6 3 7
1 4 1 6 7 3 4 5 2 3 6 2 7 5
1 6 1 3 5 7 4 3 6 2 5 4 2 7
1 5 1 7 3 4 6 5 3 2 4 7 2 6
1 5 1 6 3 7 4 5 3 2 6 4 2 7
1 5 1 4 6 7 3 5 4 2 3 6 2 7
5 1 7 1 6 2 5 4 2 3 7 6 4 3
4 1 7 1 6 4 2 5 3 2 7 6 3 5


 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
arandomguy
Guest

What’s the time complexity, and how do i calculate it here?

foobar
Guest

Do we need to run the loop for 2*n ? wouldn’t ‘n’ be sufficient?

foobar
Guest

Never mind. We need to check every combination at the second place as well.