X까지 합쳐진 주어진 숫자의 조합

Question

정말 어렵지는 않겠지 만, 나는 이것에 집착했습니다. C에서 함수를 만들 필요가 있습니다.이 함수는 주어진 숫자의 모든 가능한 조합 (반복 없음)을 계산합니다. 추가 할 때 모든 조합의 숫자 (1에서 9까지만 가능)가 지정된 합계를 제공합니다.

나는, 그래서 여기에 분명한 설명이 아니다 예 추측 : 28

까지 추가 (1 ~ 9) 5 개 숫자의 모든 세트 사람이 설명 할 수 있다면 난 정말 감사 드리겠습니다을 계산 이.

Answer 1

512 가지 선택 사항이 있으므로 결과를 쉽게 미리 계산할 수 있습니다.

는 사전 계산 :

• 빈 맵을 준비한다 (합계 => 설정 (SET (자리)))이라는 lookup. (1..9)
  • 마다 subset위한
  • sum는를 계산한다.
  • lookup에 sum 키가없는 경우 새 항목 인 빈 세트를 만듭니다.
  • 는 subset

lookup[sum]에 조회하려면 추가 할 sum :

• lookup 키 sum, 리턴 (사본) 항목이있는 경우. 그렇지 않으면 빈 세트를 반환합니다.

---

는 C의 하위 레벨 다움의 일부를 해결하기 :

지도의 INT => X는 단순히 배열이다. x의 집합은 간단히 배열 + 길이입니다.

이미 큰 키를 알고 있기 때문에지도의 배열은 정적으로 할당 할 수

, 45

당신은뿐만 아니라 세트의 가장 큰 세트를 미리 추정, 또는 (더 효율적으로) 동적 할당을 사용할 수 있습니다. 공간에 대해 신경 쓰지 않으면 쉽게 할당 할 수 있습니다 (최대 512 개 항목). 나는이 정도를 과도하게 할당하고 싶지 않으므로 동적으로 할당하는 방법을 배울 수 있다고 생각합니다.

숫자 세트는 9 비트 비트 마스크 (메모리의 16 비트)로 나타낼 수 있습니다. 그렇다면 쉽게 열거 할 수 있습니다.

lookup의 실제 유형의 스케치 :

typedef setOfDigits int16; 

struct setOfSets{ 
    setOfDigits* data; 
    int16 count; //the actual amount of sets in the set 
    int16 space; //the size of the allocated array 
} 

setOfSets lookup[46]; 

동적 할당 또는 struct의없이 lookup의 실제 유형의 스케치 :

int16 lookup[46][512]; 
int16 lookupLength[46]; 

참고가 space:=count을 동일시하는 경우가, 그렇다면 과도하게 할당하지는 않겠지 만 구현하기가 쉽지만 잠재적으로 비효율적 일 수 있습니다 (코드는 한 번 실행되므로 헤이)

물론 고급 언어 (및 C++)도 기본적으로 (자바 스크립트) 또는 표준 라이브러리 (C++, Java)를 통해 동적 배열을가집니다. C에서는 realloc을 의지해야합니다.