My C++ elegant solution with back-tracking


  • 17
    // By lovellp
    // Time: 6ms
    class Solution {
    public:
        int countArrangement(int N) {
            vector<int> vs;
            for (int i=0; i<N; ++i) vs.push_back(i+1);
            return counts(N, vs);
        }
        int counts(int n, vector<int>& vs) {
            if (n <= 0) return 1;
            int ans = 0;
            for (int i=0; i<n; ++i) {
                if (vs[i]%n==0 || n%vs[i]==0) {
                    swap(vs[i], vs[n-1]);
                    ans += counts(n-1, vs);
                    swap(vs[i], vs[n-1]);
                }
            }
            return ans;
        }
    };
    

  • 1
    Y

    @love_FDU_llp I have a question:
    why it is not
    if (vs[i]%n==0 || n%vs[i]==0) && ((vs[n-1]%(i+1))==0 || (i+1)%vs[n-1])
    in the if condition
    because you need to make sure the both pair of swap is beautiful arrangement


  • 0
    O

    @ylc0sky Each step during recursion takes care of one position at a time, i.e, n - 1. the position [i] (let's say i = 3) will be processed when recursion reaches that. That's why there's no need to worry about whether this position meets arrangement criteria in the current [n-1] step. When the vs[3] (where the input parameter n = 4) is handled in subsequent recursion, the value will be decided from the remainder elements vs[0], vs[1], vs[2], vs[3]


  • 1
    O

    said in My C++ elegant solution with back-tracking:

     int counts(int n, vector<int> vs) {
    

    can be written as

    int counts(int n, vector<int> &vs) {
    

  • 0

    Hi @onetimetry,

    Thanks! Now it's more faster. : )


  • 0
    Y

    @onetimetry Thank you for the answer. so my question here is:
    if (vs[i]%n==0 || n%vs[i]==0) {
    swap(vs[i], vs[n-1]);

    In this above code, after swap, I think it still need to make sure that i and vs[n] should also be beautiful arrangement


  • 0
    Y
    This post is deleted!

  • 0
    Y

    This is my code. what's wrong cannot figure it out

    
    
    class Solution {
    public:
        int ret = 0;
        int countArrangement(int N) {
            vector<int> v(N,0);
            for(int i=0;i<v.size();i++)
            {
                v[i] = i+1;
            }
            solve(0, v, N);
            return ret;
        }
        void solve(int pos, vector<int>& v, int length)
        {
            if(pos >=length) 
            {
                for_each(v.begin(), v.end(), [](int n){cout<<n<<" ";});
                cout<<endl;
                ret++;
                return;
            }
    
            for(int i=0;i<=pos;i++)
            {
                if(isBeauty(v[i], pos+1)&&isBeauty(v[pos],i+1))
                {                
                    swap(v[i], v[pos]);
                    solve(pos+1, v, length);         
                    swap(v[i], v[pos]);
                }         
            }
        }
        bool isBeauty(int pos, int val)
        {
            return pos%val==0 || val%pos == 0;
        }
    
    };
    

  • 0
    Y

    I'm guessing the reason you don't check if n=0 is valid is because any integer is valid in the first position of the array.


  • 1
    P

    @ylc0sky
    when n = 6, you cannot get [2 6 1 4 5 3] it should come from [2 3 1 4 5 6], but [2 3 1 4 5] is invalid when n = 5


  • 0
    Y

    @polesun You saved my life!


  • 0
    N

    @ylc0sky I have the same question with you.
    Guess the reason is:

    1. Init, every number are in the right position: nums[i] == i;(index start from 1....)
    2. Then, if nums[i]%n==0 || n%nums[i]==0 is true, then i % n || nums[n] % i is also true, both situation indicates safe to swap.
    3. And the swap keeps the property of that, so its no need to check the "(vs[n-1]%(i+1))==0 || (i+1)%vs[n-1])".

    Just guess, hope someone can give a entire proof.


  • 0
    S

    @NeoMatrix I think you are right, but if you can give an entire proof, that will be more convincing !


  • 0

    I think if you change for loop condition to
    for (int i = n-1; i>=0; i--)
    it makes me easier to understand cause it's actually verifying if the number could be divided by index while doing the permutation


  • 0
    W
    This post is deleted!

  • 0
    D

    @ylc0sky, it is not necessary to guarantee vs[n] is beautiful at position i at the time when n>i+1 because in the later loop when n=i+1 the if statement will check it. My understanding of invariant for the loop is all numbers in position [n, vs.size) are beautiful and numbers in [0,n) are not. When n==0, everything is beautiful and we count it as one.


  • 0
    M

    C++ backtracking using bool array to indicate if a number is used or not

    class Solution {
    public:
        int countArrangement(int N) {
            if(N<1) return 0;
            vector<bool> used(N+1,false);
            return dfs(N,1,used);
        }
    private:
        int dfs(int N, int i, vector<bool>& used) {
            if(i>N) return 1; // term. cond.
            int sum = 0;
            for(int num=1; num<=N; num++) {
                if(used[num]) continue;
                if(num%i!=0 && i%num!=0) continue; // co-prime
                used[num]=true;
                sum+=dfs(N,i+1,used);
                used[num]=false;
            }
            return sum;
        }
    };
    

  • 0
    S

    Hi
    Since the size of N <= 15 you can also use bitmasks and save space

    class Solution {
    public:
        int countArrangement(int N) {
            if(N <= 1)return N;
            int ans = 0 , mask = 0;
            countArrangementUtil(mask , ans , 1 ,N);
            return ans;
        }
        
        void countArrangementUtil(const int mask , int& ans , const int idx ,const int N){
            if(idx == N + 1){
                ans++ ; return;
            }
            for(int i = 1; i <= N ; ++i){
                int k = (mask & (1 << (i-1)));
                if(k == 0 && (idx%i == 0 || i%idx == 0)){
                    countArrangementUtil(mask | (1 << (i-1)) , ans , idx + 1 , N);
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.