В случае вашей первой идеи:
Ваша первая идея попробовать каждую возможную комбинацию одну за другой и проверить суммирование определенно будет работать, но проблема в том, что сложность будет очень высокой.Для этого мы можем просто сделать так:
bool recursion(int pos, int n, int sum, vector<int>&sequence) {
if (pos == n) {
if (sum == 0) return true;
else return false;
}
bool resultTakingPositive = recursion(pos + 1, n, sum + sequence[pos], sequence);
bool resultTakingNegative = recursion(pos + 1, n, sum - sequence[pos], sequence);
if (resultTakingPositive || resultTakingNegative) return true;
else return false;
}
Если существует всего n целых чисел, то это решение займет сложность времени O(2^n).Потому что в каждой позиции есть два варианта:
- Take + ve значение при суммировании.
- Take -ve значение при суммировании.
И,мы должны сделать выбор для каждого n целого числа.Итак, n умножение на 2 приводит к O (2 ^ n) временной сложности.
В случае вашей второй идеи:
Вы пытаетесь отсортироватьСначала выполните последовательность действий в порядке возрастания и присвойте знак + ve первому числу, затем вычитайте, пока не получите отрицательное число, затем снова добавьте, пока не получите положительное число.К сожалению, этот жадный подход не всегда работает.Например:
В последовательности: 5, 4, 4, 3, 2
Если мы попробуем этот подход, у нас будет: +5 -4 -4 +3 +2, что приводит к суммированию = 2.
Но мы можем сделать суммирование нулем, выполнив: +5 +4 -4 -3 -2.
Эффективный подход:
Мы можем использовать запоминание в вышеупомянутом рекурсивном решении с простой модификацией, чтобы позволить позитивную индексацию при выполнении запоминания со состояниями pos иsum.Это также называется динамическим программированием.Для этого максимально возможное значение pos * sum должно быть меньше, чтобы кэшировать их состояния в памяти, используя двумерный массив.Таким образом, сложность во времени и пространстве будет O(n * sum).Примером такого подхода с использованием кода c ++ будет:
#include<bits/stdc++.h>
using namespace std;
bool recursion(int pos, int n, int sum, vector<int>&sequence,int &baseSum, vector< vector<int> >&dp) {
if (pos == n) {
if (sum == baseSum) return true;
else return false;
}
if (dp[pos][sum] != -1) return dp[pos][sum];
bool resultTakingPositive = recursion(pos + 1, n, sum + sequence[pos], sequence, baseSum, dp);
bool resultTakingNegative = recursion(pos + 1, n, sum - sequence[pos], sequence, baseSum, dp);
dp[pos][sum] = (resultTakingPositive || resultTakingNegative);
return dp[pos][sum];
}
int main() {
vector<int>sequence;
int n, baseSum = 0;
scanf("%d",&n);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d",&x);
sequence.push_back(x);
baseSum += x;
}
vector< vector<int> >dp(n, vector<int>(2*baseSum + 1, -1));
cout<<recursion(0, n, baseSum, sequence, baseSum, dp)<<endl;
return 0;
}
Теперь, если мы хотим отслеживать знаки, используемые для суммирования 0, мы можем сделать это путем анализа рекурсивных вызовов следующим образом:
#include<bits/stdc++.h>
using namespace std;
bool recursion(int pos, int n, int sum, vector<int>&sequence,int &baseSum, vector< vector<int> >&dp) {
if (pos == n) {
if (sum == baseSum) return true;
else return false;
}
if (dp[pos][sum] != -1) return dp[pos][sum];
bool resultTakingPositive = recursion(pos + 1, n, sum + sequence[pos], sequence, baseSum, dp);
bool resultTakingNegative = recursion(pos + 1, n, sum - sequence[pos], sequence, baseSum, dp);
dp[pos][sum] = (resultTakingPositive || resultTakingNegative);
return dp[pos][sum];
}
void printSolution(int pos, int n, int sum, vector<int>&sequence,int &baseSum, vector< vector<int> >&dp) {
if (pos == n) {
cout<<endl;
return;
}
bool resultTakingPositive = recursion(pos + 1, n, sum + sequence[pos], sequence, baseSum, dp);
if (resultTakingPositive == true) {
cout<< "+ ";
printSolution(pos + 1, n, sum + sequence[pos], sequence, baseSum, dp);
} else {
cout<< "- ";
printSolution(pos + 1, n, sum - sequence[pos], sequence, baseSum, dp);
}
}
int main() {
vector<int>sequence;
int n, baseSum = 0;
scanf("%d",&n);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d",&x);
sequence.push_back(x);
baseSum += x;
}
vector< vector<int> >dp(n, vector<int>(2*baseSum + 1, -1));
if (recursion(0, n, baseSum, sequence, baseSum, dp)) { // if possible to make sum 0 then
printSolution(0, n, baseSum, sequence, baseSum, dp);
}
return 0;
}