NON Repeatitive ::: -- Print all increasing sequences of length k from first n natural numbers (Recursive)
http://www.geeksforgeeks.org/print-increasing-sequences-length-k-first-n-natural-numbers/
Geeksforgeeks.
Input: k = 2, n = 3
Output: 1 2
1 3
2 3
Input: k = 5, n = 5
Output: 1 2 3 4 5
Input: k = 3, n = 5
Output: 1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
This is a Branch and Bound type of Problem. In which you have to decide whether to "take a
number" or "not to take" a number. After that make a recursive call again.
#include<bits/stdc++.h> using namespace std; int fi(int dest,int steps,int cu) { if(cu==dest) return steps; if(abs(cu)>dest) return INT_MAX; return min(fi(dest,steps+1,steps+cu+1),fi(dest,steps+1,cu-steps-1)); } int main() { int dest,i,j; cin>>dest; cout<<fi(dest,0,0)<<endl; return 0; }
Comments
Post a Comment