[问答题]

```Input : [1, 2, 3, 4]
k = 10
Output :11
The subsequences are {1}, {2}, {3}, {4},
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4},
{1, 2, 3}, {1, 2, 4}

Input  : [4, 8, 7, 2]
k = 50
Output : 9```

`public class Main {   public static int getNumberOfMultiplySmallerThanK(int[] array, int k, int index, int multiply) {  //递归退出条件  if (index >= array.length) {  return multiply < k ? 1 : 0;  }   //索引为index的数要  return getNumberOfMultiplySmallerThanK(array, k, index + 1, multiply * array[index]) + //索引为index的数不要  getNumberOfMultiplySmallerThanK(array, k, index + 1, multiply);  }   public static void main(String[] args) {  System.out.println(getNumberOfMultiplySmallerThanK(new int[]{1, 2, 3, 4}, 10, 0, 1) - 1);  System.out.println(getNumberOfMultiplySmallerThanK(new int[]{4, 8, 7, 2}, 50, 0, 1) - 1);  } }`

```import itertools
a=input()
b=input()
a=list(a)
count=0 lt=[] for j in range(len(a)):
l=j+1  for i in itertools.combinations(a,l):
lt.append(i) for i in lt:
y = 1   for k in i:
y=1*y*int(k)  if y<b:
count=count+1 print count```

01背包
```//dp[i] 表示积为i的组合有dp[i]个
vector<int> dp(k, 0); dp[1]=1;
bool flag=0;
for (int i = 0; i < n; i++) {
// 先不考虑1
if(data[i]==1) {
flag = 1;
continue;
}
for (int j = k-1; j>0; j--) {
if (dp[j] > 0 && j * data[i] < k ) {
dp[j * data[i]] += dp[j];
}
}
}
int res = accumulate(dp.begin()+2, dp.end(), 0);
if(flag) // 如果有1
res = 2*res+1;```

```用递归 每次计算乘积值 最后判断 我这里把结果也存了并且输出
#include <iostream>
#include <vector>
#include<string.h>
using namespace std;
void  arraysum(vector<int>&a,vector<int>temp,int c,int k,int len,vector<vector<int> >&res)
{
if(len==a.size())
{
if(c<k&&!temp.empty())
res.push_back(temp);
return ;
}

arraysum(a,temp,c,k,len+1,res);
temp.push_back(a[len]);
c=a[len]*c;
arraysum(a,temp,c,k,len+1,res);
}
int main()
{
vector<int>a;
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
int len=0;
int c=1;int k=10;
vector<int>temp;
vector<vector<int> > res;
arraysum(a,temp,c,k,0,res);
for (int j = 0; j < res.size(); j++)     {         cout << endl;         for (int k = 0; k< res[j].size(); k++)         {             cout << res[j][k] << "     ";         }     }
}

```

4条回答 387浏览

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题