首页 > 试题广场 >

集合遍历

[编程题]集合遍历
  • 热度指数:1623 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
有K种颜色的小球(K<=10),每种小球有若干个,总数小于100个。
现在有一个小盒子,能放N个小球(N<=8),现在要从这些小球里挑出N个小球,放满盒子。
想知道有哪些挑选方式。注:每种颜色的小球之间没有差别。

请按数字递增顺序输出挑选小球的所有方式。

如有3种颜色,每种颜色小球的个数分别为a:1,b:2,c:3,挑出3个小球的挑法有:
003,012,021,102,111,120


输入描述:
第一行两个数字K N,分别表示小球种类数目和挑选的小球个数
第二行开始为每种小球的数目,共K行数据


输出描述:
输出所有可行的挑选方案,按升序排列
示例1

输入

3 3
1
2
3

输出

003
012
021
102
111
120
C++递归  100%通过
#include<iostream>
(720)#include<string>
#include<iomanip>
using namespace std;
int box[10];
int kind, sum;
void jisuan(int num,int box_id,long long X)
{
    long long  M = 1;
    if (num == 0)
    {
        return;
    }
    for (int q = 0; q < (kind - box_id) - 1; q++)
    {
        M = M * 10;
    }
    for (int i = 0; i <= box[box_id]; i++)
    {
        if (num == i)
        {
            cout << setfill('0') << setw(kind) << *right<< X + i * M<<endl;
        }
        if (i < num)
        {
            if (box_id != kind - 1)
            jisuan(num - i, box_id + 1, X + i * M);
        }
    }
 
}
int main()
{
    cin >> kind >> sum;
    for (int i = 0; i < kind; i++)
    {
        cin >> box[i];
    }
    jisuan(sum,0,0);
}

编辑于 2020-03-24 11:52:01 回复(2)

这道题是变相的排序题目。目的是输出0~1111,1111之间位数上的数之和为8的所有数,并从小到大排列。找到这个规律题目就好解了。

发表于 2020-02-26 12:30:37 回复(1)
回溯法,保存原始球数量的数组colorfulBalls,复制一个作为回溯时使用的剩余球数组remainBalls。在回溯的过程中,如果还需要的球数量变为0,就添加一个候选答案(用colorfulBalls的元素减去对应的remainBalls的元素,然后将数组元素拼接为一个字符串即可)到有序表中。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.TreeSet;

public class Main {
    private static TreeSet<String> results = new TreeSet<>();
    private static int[] colorfulBalls;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int k = Integer.parseInt(params[0]), n = Integer.parseInt(params[1]);
        colorfulBalls = new int[k];
        int[] remainBalls = new int[k];
        for(int i = 0; i < k; i++) {
            colorfulBalls[i] = Integer.parseInt(br.readLine());
            remainBalls[i] = colorfulBalls[i];
        }
        dfs(remainBalls, n, 0);
        for(String result: results){
            System.out.println(result);
        }
    }
    
    private static void dfs(int[] remainBalls, int rest, int depth) {
        if(rest == 0){     // 不需要球了,添加一个答案
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < remainBalls.length; i++){
                sb.append(colorfulBalls[i] - remainBalls[i]);
            }
            results.add(sb.toString());
        }
        if(rest > 0){
            for(int i = depth; i < remainBalls.length; i++){
                if(remainBalls[i] > 0){     // 第i个颜色还有球的时候就拿一个
                    remainBalls[i] --;
                    dfs(remainBalls, rest - 1, i);
                    remainBalls[i] ++;      // 回溯
                }
            }
        }
    }
}

发表于 2021-12-06 15:52:05 回复(0)
import java.util.*;
/**
*  回溯算法
*/
public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt();
        int n = scan.nextInt();    

      Map<Integer, Integer> nums = new HashMap<>();
        for (int i = 0; i < k; i++)
            nums.put(i, scan.nextInt());
                scan.close();

        traverse(new StringBuilder(), nums, 0, n);

        for (String s : result)
            System.out.println(s);
    }

    static List<String> result = new ArrayList<>();
    static int ballUsed = 0;    //记录已使用小球数量
    static boolean flag = false;

    static void traverse(StringBuilder res, Map<Integer, Integer> nums, int k, int n) {
        if (ballUsed > n) {
            flag = true;
            return;
        }
        if (k == nums.size()) {
            if (ballUsed == n)
                result.add(res.toString());
            return;
        }

        for (int i = 0; i <= nums.get(k); i++) {
            res.append(i);
            ballUsed += i;
            traverse(res, nums, k + 1, n);
            ballUsed -= i;
            res.deleteCharAt(res.length() - 1);
            if (flag) {        //剪枝,如果已使用小球超过总数n,则不再回溯
                flag = false;
                return;
            }
        }
    }
}


编辑于 2021-08-30 23:08:56 回复(0)
Python 递归
import sys
K, N = list(map(int, sys.stdin.readline().split()))
 
def backtrace(i, my_dic, cnt, res, s):
    if i == K and cnt == N:
        res.append(''.join(s))
    elif i < K:
        for use in range(my_dic[i]+1):
            if use <= N - cnt:
                s.append(str(use))
                backtrace(i+1, my_dic, cnt+use, res, s)
                s.pop()
            else:
                break

if __name__ == '__main__':
    my_dic = {}
    for i in range(K):
        my_dic[i] = int(sys.stdin.readline().strip())
    res = []
    backtrace(0, my_dic, 0, res, [])
    for r in res:
        print(r)


发表于 2019-09-02 18:19:18 回复(4)
# coding=utf-8
import sys
a = [0]*11
ans = [0]*11
k,n=0,0

def Print(k, ans):
    res = ''
    for i in range(k):
        res += str(ans[i])
    print(res)

def fun(i, n): # i可以认为是球类比的编号,ans[i]就是结果中,i类球放几个
    if n==0:  # n=0就是递归结束了,要放的球都安排好了~
        Print(k, ans)
        return
    if n<0 or k==i:
        return
    for j in range(a[i]+1):  # a[i]+1就是j可以取0~a[i]
    # 即j表示这类球放几个
        ans[i] = j
        fun(i+1, n-j)  # i+1是移动下,考虑放下一类球了~
    ans[i] = 0  # 没遍历到的ans位就是放0个球

try:
    while True:
        line1 = sys.stdin.readline().strip()
        l = list(map(int, line1.split()))
        k = l[0]  # 球共所少类
        n = l[-1] # 共需要n个球
        nums = sys.stdin.readlines()
        # a数组,index为球的类,index上的value为这类球有的数量
        a = [int(v.strip()) for v in nums]
        fun(0, n)
except:
    pass

发表于 2019-07-31 11:02:02 回复(0)
/*C++,AC百分之八十,测试用例运行时间:3ms,内存占用:376k,
 *采用迭代递归,有大佬看的话麻烦指点优化一下,谢谢~~~
*/
#include <iostream>
#include <vector>~~
#include<iterator>
using namespace std;

void demo(vector< vector<int> > *v, vector<int> *v1, int n, int l, int sum)
{
	if (l == n)
	{
		int sum1 = 0;
		for (unsigned int j = 0; j < l; j++)
		{
			sum1 += v1->at(j);
		}

		if (sum1 == sum)
		{
            copy(v1->begin(), v1->end(), ostream_iterator<int>(cout));
			cout << endl;
		}
		return;
	}
	
		for (unsigned int j = 0; j < v->at(l).size(); j++)
		{
			v1->at(l) = v->at(l).at(j);
			demo(v, v1, n, l + 1, sum);
		}
}

int main()
{
	int n = 0;
	int sum = 0;
	cin >> n >> sum;

	vector< vector<int> > v_int(n);

	for (int i = 0; i < n; i++)
	{
		int temp = 0;
		cin >> temp;

		for (int j = 0; j <= temp; j++)
		{
			v_int.at(i).push_back(j);
		}
	}

	vector<int> temp1(n);
	demo(&v_int, &temp1, n, 0, sum);

	return 0;
}

编辑于 2019-09-11 20:51:13 回复(0)
经过调试终于得到100分!通过数组实现存储取球情况,刚开始提交代码70分内存过载,后来将代码中的多余情况排除掉后所有测试案例通过!
#include <iostream>
#include<vector>
#include<numeric>
using namespace std;
struct node{
	int num;
	vector<vector<int> > v;
};
int main(){
	int K, N,Ki;
	cin >> K >> N;
	vector<node> ball(K);
	for(int i=0;i<K;i++){
		node p;
		cin>>Ki;
		ball[i].num=Ki;
	}
	if(K==1) cout<<N<<endl;
	else {
		vector<int> tmpv;
		for(int i=0;i<=ball[0].num;i++)	{
			tmpv.push_back(i);
			ball[0].v.push_back(tmpv);
			tmpv.clear();
		}
		for(int i=1;i<K;i++){	
			for(int j=0;j<ball[i-1].v.size();j++){
				for(int k=0;k<=ball[i].num;k++){
					tmpv=ball[i-1].v[j];
					tmpv.push_back(k);
					if(i==K-1){
						if(accumulate(tmpv.begin(),tmpv.end(),0)==N){
							for(int l=0;l<tmpv.size();l++) cout<<tmpv[l];
							cout<<endl;
						}
					}
					else {
						if(accumulate(tmpv.begin(),tmpv.end(),0)<=N) ball[i].v.push_back(tmpv);
					}
					tmpv.clear();
				}
			}
		}
	}
}



编辑于 2019-09-17 00:53:54 回复(0)
cdf头像 cdf
使用回溯法,nums记录当前小球剩余的数量,ans是当前的答案,nums减1时ans增加1,len记录当前的长度,使用set来对答案进行排序。
#include <bits/stdc++.h>
using namespace std;
int k,n;
vector<int> nums;
set<string > ret;
void dfs(int index,int len,string &ans){
    if(len==n){
        ret.insert(ans);return ;
    }
    for (int i=index;i>=0;i--){
        if(nums[i]>0){
            ans[i]++,nums[i]--;
            dfs(i,len+1,ans);
            nums[i]++,ans[i]--;            
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>k>>n;
    int temp;
    for (int i=0;i<k;i++){
        cin>>temp;
        nums.push_back(temp);
    }
    string ans(k,'0');
    dfs(k-1,0,ans);
    for (auto s:ret)
        cout<<s<<endl;
}

发表于 2020-03-03 19:09:45 回复(0)
import java.util.Scanner;
import java.util.List;
import java.util.LinkedList;
import java.lang.Math;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int k = sc.nextInt();
            int n = sc.nextInt();
            int[] nums = new int[k];
            for(int i = 0;i < k; i++){
                nums[i] = sc.nextInt();
            }
            
            List<String> result = new LinkedList<>();
            help(result,n,0,nums,"");
            result.forEach(System.out::println);
        }
    }
    
    protected static void help(List<String> result,int target,int start,int[] nums,String s){
        if(target == 0 && start == nums.length){
            result.add(s);
            return;
        }
        
        if(start == nums.length){
            return;
        }
        for(int i = 0;i <= Math.min(target,nums[start]);i++){
            // 取当前 target 和对应球的数量中的较小值。
            help(result,target - i,start+1,nums,s+i);
        }
    }
}

发表于 2019-08-16 17:35:16 回复(0)

用一个recursion可以解决,每次在每个位置放上可能的值,在最后检查该解是否符合题目要求(总和为n)

#include 
#include 
#include 
#include 

using namespace std;

void printVec(vector v)
{
    for (auto x : v)
        cout << x;
    cout << endl;
}

void solve(vector temp, vector b, int index, int r)
{
    if (index == temp.size())
    {
        if (r == 0)
            printVec(temp);
        return;
    }
    for (int i = 0; i <= min(b[index], r); i++)
    {
        temp[index] = i;
        solve(temp, b, index + 1, r - i);
    }
}

int main() 
{
    int k, n;
    cin >> k >> n;
    vector balls (k);
    for (int i = 0; i < k; i++)
        cin >> balls[i];
    vector v (k, 0);
    solve(v, balls, 0, n);
}
发表于 2023-05-14 09:58:10 回复(0)
// 回溯
function two(kindN, selectN, arr) {
    let ans = []
    function backup(k, target, subans) {
        if (target < 0) return
        if (k == kindN && target == 0) {        
            ans.push([...subans]);
        }

        for (let i=0; i<=arr[k]; i++) {
            subans.push(i);
            backup(k+1, target-i, subans);
            subans.pop();
        }
    }

    backup(0, selectN, []);
    return ans
}

var line;
while (line=readline()) {
    let tmp = line.split(' ');
    let K = parseInt(tmp[0]), T = parseInt(tmp[1]);
    let Arr = [];
    for (let i=0; i<K; i++) {
        Arr.push(parseInt(readline()))
    }
    
    let ans = two(K, T, Arr);
    for (let i=0; i<ans.length; i++) {
        console.log(ans[i].join(''));
    }
}

发表于 2021-09-14 11:33:03 回复(0)
1.这道题我开始采用比较笨重的方法,递归+记忆+修枝,但是因为采用记忆的手段有问题导致空间复杂度太大。后来看大神的代码发现通过及时的清除无用的记忆。(这种方法在其他回答中可见,这里不做描述)。
2.虽然上述方法能够解决该问题,但是仍然不是最佳。再继续优化的过程中,我发现这道题可以抽象成——求解各个数位上的和为n的序列。
例如:3种球,其个数分别为1,2,3。盒子中放 3 个球,抽象成求百位、十位、个位和位3的序列。
这个序列的最小值为003,下一个将3取一个放入十位(012)...这样空间的存储变得很小,且问题变得很简单。
#include <vector>
#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;
int total = 0;
int k, n;
vector<int>num;

//@FUNCTION arrange 是安排每个颜色的球的个数
//@PARAM  currentnum 是string类型的变量用来存放安排的结果,i是现在操作的第i种小球,current代表
//盒中当前已经放置的球,n表示盒中存放的最大数
void arrange(string& currentnum,int i,int &current,int n) {
    if (n - current <= 0) {
        currentnum = string(1, '0') + currentnum;
    }
    else if (num[i] - (n - current) > 0) {
        currentnum = string(1, char(n - current + '0')) + currentnum;
        current += (n - current);
    }
    else {
        currentnum = string(1, char(num[i] + '0')) + currentnum;
        current += num[i];
    }
}  //@FUNCTION dealCarry 处理进位,当前数的下一个数是将数的最后一位减1,加到上一位中。
//这里我采用的思想是来源于字典排序如何获取下一个序列。
//@PARAM N代表当前数的大小,index表示可以进的位。
bool dealCarry(string &N,int index) {
    while (index>0&&N[index-1]-'0'+1>num[index-1]) {
        --index;
    }
    if (index <= 0) {
        return false;
    }
    int total_ = 0;
    for (int i = index; i < N.size(); ++i) {
        total_ += (N[i] - '0');
    }
    --total_;

    string currentnum;
    int current = 0;
    for (int i = num.size() - 1; i >= index; --i) {
        arrange(currentnum, i, current, total_);
    }
    N[index - 1] += 1;
    N = string(N, 0, index) + currentnum;
    return true;
}

//@FUNCTION  permutation 是采用进位的方法获取下一个序列
bool permutation(string& N) {
    int i = N.size()-1;
    for (; i > 0; --i) {
        if (N[i] != '0')break;
    }
    if (dealCarry(N, i)) {
        return true;
    }
    return false;
}

int  main() {
    
    cin >> k >> n;
    num = vector<int>(k, 0);
    for (int i = 0; i < k; ++i) {
        cin >> num[i];
        total += num[i];
    }
    string currentnum;
    int current = 0;
    for (int i = k - 1; i >= 0; --i) {
        arrange(currentnum,i, current,n);
    }
    if (current == n) {
        cout << currentnum << endl;
        while (permutation(currentnum)) {
            cout << currentnum << endl;
        }
    }
    return 0;    
}

编辑于 2020-05-16 18:09:57 回复(0)

c++ dfs AC100

#include 
(849)#include 
using namespace std;
void dfs(vector a, int n, int index, vector res)
{
    if (index < a.size() - 1)
    {
        for (int i = 0; i <= a.at(index); i++)
        {
            if (i <= n)
            {
                res[index] = i;
                dfs(a, n - i, index + 1, res);
            }
        }
    }
    else
    {
        if (n <= a.at(index))
        {
            res[index] = n;
            for (int k = 0; k < res.size(); k++)
                cout << res.at(k);
            cout << endl;
        }
    }
    return;
}
int main()
{
    int K, N, i;
    cin >> K >> N;
    vector a;
    for (int j = 0; j < K; j++)
    {
        cin >> i;
        a.push_back(i);
    }
    int index = 0;
    vector res;
    for (int j = 0; j < K; j++)
    {
        res.push_back(0);
    }
    dfs(a, N, index, res);
    return 0;
}
编辑于 2020-05-10 13:03:11 回复(0)
只通过了70%用例,时间复杂度过大,暂时没想到优化的方法

#include <iostream>
(720)#include <vector>
#include <string>
(765)#include <set> 
using namespace std; 
set<string> res;
vector<int> path;
//先选1个第一个,再选两个第2个与先选两个第二个再选一个第一个重复 ,将vector<string> res改为set<string>  res后解决 
void dfs(int n,vector<int> nums,string path){
	if(n==0){ //只要次数选完了,就加入path 
		res.insert(path);
		return;
	}
	for(int i=0;i<nums.size();i++){
		if(nums[i]==0) continue;		

		path[i]+=1;
		nums[i]-=1;
		
		dfs(n-1,nums,path);
		//回溯 
		nums[i]+=1;
		path[i]-=1; 
	}	
}
int main(void){
	
    int M,N;
  cin>>M>>N;
  vector<int> num;
  string path;
  for(int i=0;i<M;i++) {
    int t;
	cin>>t;
	num.push_back(t);
	path+='0';
    }
  dfs(N,num,path);
  for(auto i:res) cout<<i<<endl;
  return 0;
}


发表于 2020-02-26 12:46:56 回复(0)
run1方法是递归的 只能通过80的case后面就超时了 后面参照评论区方法改为循环 时间上可以通过
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static List<Integer> path = new ArrayList<>();

    public static void print(List<Integer> l, int k) {
        StringBuilder sb = new StringBuilder();
        l.forEach(u -> sb.append(u));
        for (int i = l.size(); i < k; i++) {
            sb.append(0);
        }
        System.out.println(sb.toString());
    }
    public static void run(int[] colors, int k, int n, int level) {
        if (n == 0) {
            print(path, k);
            return;
        }
        if (level >= k) {
            return;
        }
        for (int i = 0; i <= colors[level]; i++) {
            path.add(i);
            run(colors, k, n - i, level + 1);
            path.remove(path.size() - 1);
        }
    }

    private static List<List<Integer>> turn1 = new ArrayList<>();

    public static void run_2(int[] colors, int k, int n, int level) {
        if (k == 1) {
            System.out.println(n);
            return;
        }
        for (int i = 0; i <= colors[0]; i++) {
            turn1.add(Arrays.asList(i));
        }
        List<Integer> temp;
        for (int i = 1; i < k; i++) {
            List<List<Integer>> lastTurn = turn1;
            List<List<Integer>> nowTurn = new ArrayList<>();
            for (int j = 0; j < lastTurn.size(); j++) {
                for (int z = 0; z <= colors[i]; z++) {
                    temp = new ArrayList<>();
                    temp.addAll(lastTurn.get(j));
                    temp.add(z);
                    if (i == k-1) {
                        if (temp.stream().reduce(0, (u1, u2)->u1 + u2) == n) {
                            print(temp, k);
                        }
                    } else {
                        if (temp.stream().reduce(0, (u1, u2)->u1 + u2) <= n) {
                            nowTurn.add(temp);
                        }
                    }
                }
            }
            turn1 = nowTurn;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int k = scanner.nextInt();
            int n = scanner.nextInt();
            int[] colors = new int[k];
            for (int i = 0; i < k; i++) {
                colors[i] = scanner.nextInt();
            }
            run_2(colors, k, n, 0);
        }
    }
}


编辑于 2019-10-04 18:39:55 回复(0)
AC100%,普通的回溯解法
#include <iostream>
#include<vector>
#include<deque>
#include<string>
#include<numeric>
using namespace std;
void dfs(vector<int> ballmax, vector<int>& ball,deque<string>&res,int target,int index) 
{
    if (accumulate(ball.begin(),ball.end(),0)==target) {
        string r = "";
        for (auto c : ball)
            r += to_string(c);
        res.push_front(r);
        return;
    }
    if (accumulate(ball.begin(), ball.end(), 0) > target) {
        return;
    }
    for (int i = index; i < ballmax.size(); i++) {
        if (ball[i] < ballmax[i]) {
            ball[i]++;
            dfs(ballmax, ball,res, target,i);
            ball[i]--;
        }
    }
    return;
}
int main()
{
    int K, N;
    cin >> K >> N;
    vector<int> ballmax;
    vector<int> ball(K, 0);
    deque<string> res;
    while (K--) {
        int tmp;
        cin >> tmp;
        ballmax.push_back(tmp);
    }
    dfs(ballmax, ball,res, N,0);
    for (auto s : res)
        cout << s << endl;;

}
发表于 2019-09-05 13:09:34 回复(0)
//AC20%,复杂度过大,我用的暴力法,排列C(N,M),从N个球选出M个,然后判断选出的每个球来自哪//个位置
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
vector<int> sto;
set<string> sd;
void get_combinations(int n, int m, int* result, int len)
{
    int a[10] = {0};
    vector<int> as;
    if (m == 0)
    {
        for (int i = 0; i < len; i++)
        {     
            if (result[len - 1 - i] <= sto[0])
            {
                a[0]++;
                
                continue;
            }
            else 
            {
                for (int k = 0; k < sto.size() - 1; k++)
                {

                    if (result[len - 1 - i]>sto[k] && result[len - 1 - i] <= sto[k + 1]) a[k + 1]++;
                }
            }
        }
        string s = "";
        for (int z = 0; z < len; z++)
        {
        //    cout << a[z];
            s+=to_string(a[z]);
        }
        sd.insert(s);
        //cout << endl;         
        return;
    }
    for (int i = n; i >= m; i--)
    {
        result[m - 1] = i;
        get_combinations(i - 1, m - 1, result, len);
    }
}
int main()
{
    int K, N;
    int temp;
    int sum = 0;
    cin >> K;
    cin >> N;
    int store[1000];
    for (int i = 0; i < K; i++)
    {
        cin >> temp;
        sum += temp;
        sto.push_back(sum);
    }

    //cout << sum << endl;
    get_combinations(sum, N, store, N);
    set<string>::iterator iter = sd.begin();
    while (iter != sd.end())
    {
         
            cout << *iter<<endl;
            iter++;
    }    
    system("PAUSE");
    return 0;
}

发表于 2019-09-04 17:16:49 回复(0)
可以利用深度优先遍历和广度优先遍历的思路
发表于 2019-08-22 19:46:28 回复(0)
public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int k=sc.nextInt();
            int n=sc.nextInt();
            int [] nums=new int[k];
            for(int i=0;i<k;i++){
                nums[i]=sc.nextInt();
            }
            Stack<String> stack=new Stack<String>();
            helper(nums,n,0,stack,"");
            while(!stack.isEmpty()){
            System.out.println(stack.pop());
            }
        }
        
    }
    private static void helper(int [] nums,int target,int index,Stack<String> stack,String string){
        if(index==nums.length&&target==0){
            stack.push(string);
            return;
        }
        int nextTarget=0;
        for(int i=Math.min(target,nums[index]);i>=0;i--){
            nextTarget=target-i;
            helper(nums,nextTarget,index+1,stack,string+"i");
        }
    }

发表于 2019-08-01 10:43:24 回复(4)