Move weighting scale alternate under given constraints | C ++ program to print weights for alternating the weighting scale ; DFS method to traverse among states of weighting scales ; If we reach to more than required steps , return true ; Try all possible weights and choose one which returns 1 afterwards ; Try this weight only if it is greater than current residueand not same as previous chosen weight ; assign this weight to array and recur for next state ; if any weight is not possible , return false ; method prints weights for alternating scale and if not possible prints ' not ▁ possible ' ; call dfs with current residue as 0 and current steps as 0 ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool dfs ( int residue , int curStep , int wt [ ] , int arr [ ] , int N , int steps ) { if ( curStep > steps ) return true ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] > residue && arr [ i ] != wt [ curStep - 1 ] ) { wt [ curStep ] = arr [ i ] ; if ( dfs ( arr [ i ] - residue , curStep + 1 , wt , arr , N , steps ) ) return true ; } } return false ; } void printWeightsOnScale ( int arr [ ] , int N , int steps ) { int wt [ steps ] ; if ( dfs ( 0 , 0 , wt , arr , N , steps ) ) { for ( int i = 0 ; i < steps ; i ++ ) cout << wt [ i ] << " ▁ " ; cout << endl ; } else cout << " Not ▁ possible STRNEWLINE " ; } int main ( ) { int arr [ ] = { 2 , 3 , 5 , 6 } ; int N = sizeof ( arr ) / sizeof ( int ) ; int steps = 10 ; printWeightsOnScale ( arr , N , steps ) ; return 0 ; }