首页 > 试题广场 >

集合遍历

[编程题]集合遍历

热度指数：1627 时间限制：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

输入

输出

算法知识视频讲解

Java

Pekin

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)