算法：在一个集合中选取所有符合条件的元素组合

一时失言乱红尘 2022-08-08 05:08 16阅读 0赞

做了好几个题目都遇到题中的场景。于是写了个算法，元素组合条件是求和。  
**算法能适应的场景要求组合条件可以拆分的，有对应的逆运算。**

代码实现的是取三个元素和在40~60之间的组合。循环n（testList.size()）次可以获取所有符合条件的组合。

import org.junit.Test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    
    public class JunitTest { 
    
        @Test
        public void test() throws InterruptedException {
            List<Integer> testList = new ArrayList<Integer>();
            testList.add(5);
            testList.add(10);
            testList.add(15);
            testList.add(20);
            testList.add(25);
            testList.add(30);
            testList.add(35);
    
            System.out.println(select(40, 60, 3, testList));
        }
    
        //递归选择指定个数　符合条件的所有组合
        private List<List<Integer>> select(int min, int max, int count, List<Integer> resourceList) {
            if (count == 1) {
                return eligible(min, max, resourceList);
            } else {
                List<List<Integer>> rsList = new ArrayList<List<Integer>>();
    
                Integer i = resourceList.remove(0);
    
                if (resourceList.size() >= count) {
                    List<Integer> tmpList = new ArrayList<Integer>(resourceList);
                    //去掉第一个元素 剩余元素中的组合
                    rsList.addAll(select(min, max, count, tmpList));
                }
                //个数--，条件拆分 min - i, max - i
                rsList.addAll(assembly(i, select(min - i, max - i, --count, resourceList)));
                return rsList;
            }
        }
    
        //选择符合条件的结果
        private List<List<Integer>> eligible(int min, int max, List<Integer> resourceList) {
            List<List<Integer>> rsList = new ArrayList<List<Integer>>();
            for (Integer i : resourceList) {
                if (i >= min && i <= max) {
                    List<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(i);
                    rsList.add(tmp);
                }
            }
            return rsList;
        }
    
        //组合
        private List<List<Integer>> assembly(Integer base, List<List<Integer>> resourceList) {
            List<List<Integer>> rsList = new ArrayList<List<Integer>>();
    
            for (List<Integer> list : resourceList) {
                list.add(base);
                rsList.add(list);
            }
    
            return rsList;
        }
    }