给定一个正整数集合X={x1,x2,x3...,xn}和一个正整数y，设计回溯算法，求集合X的一个子集Y，使得Y中元素之和等于y
//8_5 #include<iostream> #include<vector> using namespace std; vector<int> X = { 1,2,3,4,5,6 }, result, visited(X.size()); int y = 10; void dfs(const int& sum) { if (sum == y) { cout << y << " = "; for (int i = 0; i < result.size(); i++) cout << (i ? "+" : "") << X[result[i]]; cout << endl; } else for (int i = result.empty() ? 0 : result.back() + 1; i < X.size(); i++) { if (!visited[i]&&sum+X[i]<=y) { result.push_back(i); visited[i] = 1; dfs(sum + X[i]); visited[i] = 0; result.pop_back(); } } } int main() { dfs(0); return 0; }
