lintcode---质数乘积

题目描述：
给定一个无重复的质数数组arr，每个质数最多使用一次，求所有无重复的乘积并从小到大排序。

注意事项：
2 <= |arr| <= 9
2 <= arr[i] <= 23

样例：
给出 arr = [2,3], 返回 [6]。

解释：
2*3=6。
给出 arr = [2,3,5], 返回 [6,10,15,30]。

解释：
2*3=6, 2*5=10, 3*5=15, 2*3*5=30。

思路讲解：
首先我们分析这个题目，其就是将找出这些数，然后对其进行排序，首先我们看一下如何找出这些数，我们可以看出这些数都是任意两个数、任意三个数、一直到所有的数。然后就是将任意N个数的所有组合找出来，这个地方我们用到的是深搜（dfs）,通过数组的顺序将其找出，
例如：
arr=[2,3,5,7]我们找到2个数的任意组合。首先找到2，然后第二数是3，5，7接着是3，其第二个数是5，7、最后是5，其第二个数是7这样就得到了两个的所有组合。

代码详解：

class Solution {
public:/*** @param arr: The prime array* @return: Return the array of all of prime product*/vector<int> getPrimeProduct(vector<int> &arr) {// Write your code hereint len = arr.size();vector<int>res;for(int i=2;i<=len;i++){//质数组合方式的个数dfs(arr,0,i,1,0,res);}sort(res.begin(),res.end());//对其进行排序return res;}void dfs(vector<int>arr,int start,int len,int sum,int cur,vector<int>&res){//用来递归循环找出n个数的任意组合if(cur==len){res.push_back(sum);//cout<return ;}int arr_size=arr.size();for(int i=start;i1,len,sum*arr[i],cur+1,res);}}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！