停止遞歸算法

Question

有10個數字具有以滿足以下方程：

（A [0] + A [1] + [3] + A [4]）= S

（a [2] + a [1] + a [9] + a [8]）= S（a [9] + a [0] + a [7] + a [8]）= S

（一個[2] + [3] + A [5] + A [6]）= S

（A [8] + A [7] + A [5] + A [4 ]）= S

我有一個數組中的10個數字，並通過使用遞歸排列算法，我試圖找到所有可能的排列，以檢查數字是否滿足上述方程。 只要找到正確的排列，我希望程序返回true並停止生成其他排列。這裏是代碼，但它總是返回false。 例如對於數字1,2,3,4,5,6,8,9,10,12和S = 24，我們有一個數字：1,8,2,12,3,6,4,10， 5,9 但算法返回false！

bool permute(int *array,int i,int length, int S) { 


    if (length == i){ 

    if(check(array, S)) 
      return true; 
     else 
     return false; 

    } 
    int j = i; 
    for (j = i; j < length; j++) { 
    swap(array+i,array+j); 
    if(check(array, S)) 
      return true; 
    permute(array,i+1,length, S); 


    swap(array+i,array+j); 
    if(check(array, S)) 
      return true; 
    } 

    return false; 
} 

bool check(int* a, int S){ 
    if((a[0]+a[1]+a[3]+a[4]) ==S && (a[9]+a[0]+a[7]+a[8]) ==S && (a[2]+a[1]+a[9]+a[8]) ==S && (a[2]+a[3]+a[5]+a[6]) ==S && (a[8]+a[7]+a[5]+a[4]) ==S) 
      return true; 

    return false; 
} 

Answer 1

您必須解決退貨狀態。 permute(array,i+1,length, S);返回一個狀態 - 在這種情況下檢查它是否爲true並返回： if(permute(array,i+1,length, S)) return true;。