给定一个数t，以及n个整数，在这n个数中找到加和为t的所有组合
【题目】给定一个数t，以及n个整数，在这n个数中找到加和为t的所有组合，例如t = 4, n = 6,这6个数为 [4, 3, 2, 2, 1, 1],这样输出就有4个不同的组合它们的加和为4: 4, 3+1, 2+2, and 2+1+1. 请设计一个高效算法实现这个需求。-----阿里2011实习生笔试题
之前只是看了一下网上这个题的写法没自己动手写，以下为自己所写的程序。
注：此题可与创新工厂的那个题目（http://blog.csdn.net/zhizunwudi/article/details/11709115）对比着看一下，两者有点不同：本题数组中数字是有限的，而创新工场的那个题目每一个数字有无限个。
- int partition(int *a,int low,int high)
- {
- int pivotKey=a[low];
- while(low<high)
- {
- while (low<high && pivotKey<=a[high])
- high--;
- swap(a[low],a[high]);
- while(low<high && pivotKey>=a[low])
- low++;
- swap(a[low],a[high]);
- }
- return low;
- }
- void QSort(int *a,int low,int high)
- {
- if (low<high)
- {
- int pivot=partition(a,low,high);
- QSort(a,low,pivot);
- QSort(a,pivot+1,high);
- }
- }
- void QucikSort(int *a,int n)//自己写的快排
- {
- QSort(a,0,n-1);
- }
- void PrintCombination(int *a,int n,int sum,vector<int>& vec)
- { //a为输入数组，n为数组长度，sum为待查找的和，vec用于保存查找到的组合
- if (sum==0)
- {
- vector<int>::iterator iter=vec.begin();
- for (;iter!=vec.end();iter++)
- {
- cout<<*iter<<" ";
- }
- cout<<endl;
- return;
- }
- else if(sum<0 || n<=0)
- return;
- vec.push_back(a[0]);//a[0]即*a，注指针a是变化的，每次指向后一个
- PrintCombination(a+1,n-1,sum-a[0],vec);
- vec.pop_back()；
- while(*a == *(a+1) && a < a+n) //【重要】跳过重复的数字
- a++;
- PrintCombination(a+1,n-1,sum,vec);
- }
- void main()
- {
- int a[8]={8,3,6,5,7,2,4,1};
- cout<<"原来的数组：";
- PrintArray(a,8);
- QucikSort(a,8);
- cout<<"排序后数组：";
- PrintArray(a,8);
- cout<<"-----------------------------"<<endl;
- vector<int> vec;
- int sum=10;
- cout<<"和为"<<sum<<"的组合如下："<<endl;
- PrintCombination(a,8,sum,vec);
- }
【注】：感觉对数组“排序”的作用就是为了跳过重复的数字，如果没有重复数字，完全不需要对数组进行排序。
测试1：（排序情况）
测试2：（不排序情况，前提是无重复数字）
测试3：（不跳过重复数字）
测试4：（跳过重复数字）
【题目】给定一个数t，以及n个整数，在这n个数中找到加和为t的所有组合，例如t = 4, n = 6,这6个数为 [4, 3, 2, 2, 1, 1],这样输出就有4个不同的组合它们的加和为4: 4, 3+1, 2+2, and 2+1+1. 请设计一个高效算法实现这个需求。-----阿里2011实习生笔试题
之前只是看了一下网上这个题的写法没自己动手写，以下为自己所写的程序。
注：此题可与创新工厂的那个题目（http://blog.csdn.net/zhizunwudi/article/details/11709115）对比着看一下，两者有点不同：本题数组中数字是有限的，而创新工场的那个题目每一个数字有无限个。
- int partition(int *a,int low,int high)
- {
- int pivotKey=a[low];
- while(low<high)
- {
- while (low<high && pivotKey<=a[high])
- high--;
- swap(a[low],a[high]);
- while(low<high && pivotKey>=a[low])
- low++;
- swap(a[low],a[high]);
- }
- return low;
- }
- void QSort(int *a,int low,int high)
- {
- if (low<high)
- {
- int pivot=partition(a,low,high);
- QSort(a,low,pivot);
- QSort(a,pivot+1,high);
- }
- }
- void QucikSort(int *a,int n)//自己写的快排
- {
- QSort(a,0,n-1);
- }
- void PrintCombination(int *a,int n,int sum,vector<int>& vec)
- { //a为输入数组，n为数组长度，sum为待查找的和，vec用于保存查找到的组合
- if (sum==0)
- {
- vector<int>::iterator iter=vec.begin();
- for (;iter!=vec.end();iter++)
- {
- cout<<*iter<<" ";
- }
- cout<<endl;
- return;
- }
- else if(sum<0 || n<=0)
- return;
- vec.push_back(a[0]);//a[0]即*a，注指针a是变化的，每次指向后一个
- PrintCombination(a+1,n-1,sum-a[0],vec);
- vec.pop_back()；
- while(*a == *(a+1) && a < a+n) //【重要】跳过重复的数字
- a++;
- PrintCombination(a+1,n-1,sum,vec);
- }
- void main()
- {
- int a[8]={8,3,6,5,7,2,4,1};
- cout<<"原来的数组：";
- PrintArray(a,8);
- QucikSort(a,8);
- cout<<"排序后数组：";
- PrintArray(a,8);
- cout<<"-----------------------------"<<endl;
- vector<int> vec;
- int sum=10;
- cout<<"和为"<<sum<<"的组合如下："<<endl;
- PrintCombination(a,8,sum,vec);
- }
【注】：感觉对数组“排序”的作用就是为了跳过重复的数字，如果没有重复数字，完全不需要对数组进行排序。
测试1：（排序情况）
测试2：（不排序情况，前提是无重复数字）
测试3：（不跳过重复数字）
测试4：（跳过重复数字）