DFS倍数 记录一个面试题

    现在给你N个整数，从中和选取3个数的和，刚好可以组成M的倍数，请问存在多少种不同的方案？相同的一组数如果次序不同只能算作是一个方案，不同的位置的相同的数字只能当作同一个数字看待，例如[2,3,3,4] 从中选取三个数字组成3的倍数 只有一种方案（2,3,4）
方法一 暴力二进制枚举 （通过了但是时间复杂度有一些高

        public List> beiShu(int[] nums, int m) {
            List> res = new ArrayList<>();
            List tmp = new ArrayList<>();
            Set ans = new TreeSet<>();
            Arrays.sort(nums);
            int n = nums.length;
            int cnt = 0;
            for (int i = 0; i < 1 << n; i++) {
                cnt = 0;
                tmp = new ArrayList<>();
                int sum = 0;
                for (int j = 0; j < n; j++) {
                    int a = i >> j;
                    if ((a & 1) == 1) {
                        cnt++;
                        sum += nums[j];
                        tmp.add(nums[j]);
                    }
                }
                if (sum % m == 0 && cnt == 3 && !chongFu(res, tmp))
                    res.add(tmp);
            }
            return res;
        }


        public boolean chongFu(List> res, List ans) {
            for (int i = 0; i < res.size(); i++) {
                if (res.get(i).size() == ans.size()) {
                    int j;
                    for (j = 0; j < ans.size(); j++) {
                        if (res.get(i).get(j) != ans.get(j))
                            break;
                    }
                    if (j == ans.size()) return true;
                }
            }
            return false;
        }


      

方法2 DFS 组合去重问题

        
        List> lists = new ArrayList<>();
        Deque deque = new linkedList<>();
        int sum = 0;

        public List> beiShu1(int[] nums, int m) {
            int n = nums.length;
            Arrays.sort(nums);
            dfs(nums, m, 0);
            return lists;
        }

        public void dfs(int nums[], int beiShu, int index) {

            if (sum % beiShu == 0 && sum!=0 && deque.size()==3) {
                lists.add(new ArrayList<>(deque));
                return ;
            }
            if(index>=nums.length)return;
            for(int i=index;i 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                sum+=nums[i];
                deque.push(nums[i]);
                dfs(nums,beiShu,i+1);
                int tmp=deque.pop();
                sum-=tmp;
            }

        }
    }