C++ 深度优先搜索 (DFS) 算法求解集合子集问题

这是一种基于深度优先搜索 (DFS) 的求解算法，用于求解集合的子集中元素之和等于给定值 k 的最小子集。具体实现过程如下：

1. 定义全局变量 a，n，k，minpath，minn。

2. 定义函数 disppath()，用于输出一个解。它遍历存放最优解的 minpath，输出其中的元素，并输出元素个数 minn。

3. 定义函数 dfs()，用于求解算法。它接受三个参数：path，sum，start。其中，path 存放一个子集，sum 存放 path 中元素之和，start 表示从 a 数组的第 start 个元素开始选择。dfs() 的实现思路如下：

   a. 如果 sum 等于给定值 k，表示找到了一个解，比较 path 的元素个数是否小于 minn，如果是，更新 minn 和 minpath。

   b. 如果 start 大于等于 n，表示已经选择完了所有元素，返回。

   c. 不选当前元素，递归调用 dfs()，start 加 1。

   d. 选当前元素，将其加入 path，sum 加上当前元素的值，递归调用 dfs()，start 加 1。

4. 在 main() 函数中定义 path，初始为空集，调用 dfs() 函数，开始搜索。最后输出存放最优解的 minpath。

本算法的时间复杂度为 O(2^n)，因为对于每个元素，都有选或不选两种情况，总共有 2^n 种情况。空间复杂度为 O(n)，因为需要存放一个子集的空间。

#include <stdio.h>
#include <vector> //vector是一个能够存放任意类型的动态数组容器
using namespace std; 
int a[]={1,2,3,4,5,6}; 
int n=6,k=10; 
vector<int>minpath;   //存放最优解
int minn=n;   //最多选择n个元素
void disppath()   //输出一个解
{
  printf(' 选择的元素:');
  for (int j=0;j<minpath.size();j++)
    printf('%d ',minpath[j]); 
  printf('元素个数=%d
',minn);
}
void dfs(vector<int>path,int sum,int start) //求解算法
{
  if (sum==k)
  {
    if (path.size()<minn)
    {
      minn=path.size();
      minpath=path;
    }
    return;
  }
  else
  {
    if (start>=n) return; 
    dfs(path,sum,start+1); 
    path.push_back(a[start]); 
    dfs(path,sum+a[start],start+1);
  }
}
int  main(){
  vector<int> path; //path 存放一个子集
  dfs(path,0,0);
  printf('最优解:
');
  disppath();
}