간격없이 배열의 모든 숫자 조합을 얻는 가장 빠른 방법

Question

가능한 모든 숫자 조합 조합의 합계를 계산해야합니다 (합계가 아닌 개별 합계). 조합은 숫자를 건너 뛸 수 없습니다.

y> x의 경우 [x]와 [y] 사이에 모든 숫자를 추가해야합니다.

(n) + (n-1) + (n-2) + ... + 1이므로 n = 5 인 경우 15 조합이 있습니다.

나는 가능한 한 빨리해야하며 공간은 문제가되지 않습니다.

편집 : 2

unsigned long long r_all = 0; 
std::vector<int> g_seentimes(m); 

for(int i = 0; i<n; i++) 
    r_all += w[z]; 
    if(r_all > r){ 
     r = r_all; 
    } 
} 

for(int j = 0; j<n; j++){ 

    unsigned long long r_temp = r_all; 

    for(int i = 0; i<(n-j); i++){ 

     r_temp -= w[n-i]; 

     if(r_temp > r){ 
      r = r_temp; 
     } 
    } 

    r_all -= w[y]; 

    if(r_all > r){ 
      r = r_all; 
    } 

} 

및

for(int i = 0; i < n; i++){ 
    unsigned long long r_temp = 0; 
    for(int j = 0; j<(n-i); j++){ 
     r_temp += w[i+j]; 
     if(r_temp > r){ 
      r = r_temp; 
     } 
    } 
} 
//r is the answer 

편집 : 나는 시도가 원래 경우, 예상 출력이 가능한 최대 수입니다,하지만 난 privided 예 버전을 simplyfied되는 두 개 이상의 조합에서 같은 수의 당신은 {5, 3, 5, 3, 1} = 1, 그러나 {5, 3, 1} = 9의 값을 추가하지 마십시오. 나는 그 부분을 알아 냈습니다. 모든 조합을 극복 할 수있는 가장 빠른 방법.

편집 3 : @Tuan333은 조합의 수에 대한 질문과 내가 그것을 보여 쉬울 것 같아요 :

X- chosen, x-unchosen 
n = 5 

XXXXX XXXXx XXXxx XXxxx Xxxxx 
xXXXX xXXXx xXXxx xXxxx 
xxXXX xxXXx xxXxx 
xxxXX xxxXx 
xxxxX 

Answer 1

먼저 누적 부분합의 배열을합니다. 따라서 숫자가 a = [1, 2, 3, 4, 5] 인 경우 해당 배열은 b = [0, 1, 3, 6, 10, 15]이됩니다. (두 번째 배열은 하나의 큰, 그래서 내가 처음에 빈 합계를 포함합니다. 이제

관찰의 i 일의 합을 a이 b[j+1] - b[i] 인의 j 번째 요소를 통해. 그래서 지금 당신은 이중 루프를 할 단지 수 ., 당신이 될 것입니다 숫자의 수를 추적 각각 "블록"에 대한

X- chosen, x-unchosen 
n = 5 

Xxxxx 
xXxxx 
xxXxx 
xxxXx 
xxxxX 

XXxxx 
xXXxx 
xxXXx 
xxxXX 

XXXxx 
xXXXx 
xxXXX 

XXXXx 
xXXXX 

XXXXX 

: 여기

Answer 2

하지 우아한 @btilly 등의 솔루션,하지만 당신이 필요로하는 모든 시퀀스를 생성 할 수있는 직관적 인 방법 당신의 하위 시퀀스에서 (blockLength라고 부르 자) 필요한 하위 시퀀스를 얻기 위해 원래 배열을 반복하기 만하면됩니다. 현재 하위 시퀀스의 길이가 blockLength이면 주변 (원래 배열 길이 - blockLength) 번째 항목에서 종료해야합니다. 다음은 모든 서브 시퀀스를 생성하는 코드 (Java)입니다. 반복되는 숫자가있는 경우 사전 처리를 통해 숫자를 모두 제거 할 수 있습니다.

int[] a = {5,3,1}; 
for(int subSeqLength = 1; subSeqLength <= a.length; subSeqLength++){ 
    for(int j = 0; j + subSeqLength <= a.length; j++){ 
     for(int k = j; k <j+subSeqLength; k++) 
      System.out.print(a[k]+" "); 
     System.out.println(); 
    } 
}