부분 합 재귀 ++

Question

이것은 그러나,이 솔루션 만 참 또는 거짓 값을 반환 true 또는 주어진 세트의 목표 값

bool subsetSumExists(Set<int> & set, int target) { 
    if (set.isEmpty()) { 
     return target == 0; 
    } else { 
     int element = set.first(); 
     Set<int> rest = set - element; 
     return subsetSumExists(rest, target) 
     || (subsetSumExists(rest, target- element)); 
    } 
} 

에서 거짓 얻는 용액 중의 하나이다. 하위 집합에 포함 된 요소를 가져 오는 것이 가능합니다 (함께 추가하면 대상과 동일하게 설정됩니다).

동적 프로그래밍을 사용해야합니까? Coz 내가 아는 .. 재귀가 실제로 스택을 구축하고 함수가 값을 반환하면 프레임 안의 값도 무시됩니다.

그래서 목표 값과 동일한 요소를 얻을 수 있습니까?

개체를 문제의 해결 방법으로 전달하고 있습니까?

는 프로그램 조금을 최적화 할 수 있습니다 당신에게 모든

Answer 1

먼저 감사 - 검사 대상이 0 경우하고 있는지 항상 true을 반환합니다. 이제 필요한 것은 이미 사용했던 요소를 저장하는 것입니다. 글로벌 "스택"(실제로 반복 할 수 있도록 vector)을 사용하여이를 수행하는 방법을 보여줄 것입니다. 왜냐하면 코드가 이해하기 쉽기 때문입니다.하지만 함수 또는 함수를 참조하여 전달할 수도 있습니다. 다른 방식으로 글로벌화하지 마십시오. 그런데 stl 컨테이너는 set이 아니고 Set이라고합니다.

vector<int> used; 
bool subsetSumExists(Set<int> & set, int target) { 
    if (target == 0) { 
     cout << "One possible sum is:\n"; 
     for (int i = 0; i < used.size(); ++i) { 
      cout << used[i] << endl; 
     } 
     return true; 
    } else if(set.empty()) { 
     return false; 
    }else { 
     int element = set.first(); 
     Set<int> rest = set - element; 
     used.push_back(element); 
     if (subsetSumExists(rest, target- element)) { 
      return true; 
     } else { 
      used.pop_back(); 
     } 
     return subsetSumExists(rest, target); 
    } 
} 

희망이 있습니다.