import java.util.*;
class Main{
    static int[] w=new int[36];
    static int m;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        m=sc.nextInt();
        for(int i=0;i<n;i++){
            w[i]=sc.nextInt();
        }
        List<Integer> A=new ArrayList<Integer>();
        List<Integer> B=new ArrayList<Integer>();
        dfs(0,n/2,0,A);
        dfs(n/2,n,0,B);
        Collections.sort(A);
        Collections.sort(B);
        int res=(A.get(A.size()-1)+B.get(B.size()-1))%m;
        for(int i=0,j=B.size()-1;i<A.size();i++){
            //因为是排过序的，所以找到的第一个B[j]即可满足最大的需求，无需接着往前遍历B
            while(A.get(i)+B.get(j)>=m) j--;
            if(j>=0) 
                res=Math.max(res,(A.get(i)+B.get(j))%m);
        }
        System.out.println(res);
    }
    //选，不选 得到所有情况的集合
    public static void dfs(int s,int e,int res,List<Integer> list){
        if(s==e){
            list.add(res);
            return;
        }
        else{
            dfs(s+1,e,res,list);
            dfs(s+1,e,(res+w[s])%m,list);
        }
    }
}

import java.util.*;
class Main{
    static int N,K;
    static String str;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        N=sc.nextInt();
        K=sc.nextInt();
        str=sc.next();
        //dfs传入参数：
        //当前比较到的数的位置u,当前使用了的乘号个数k,当前组合成的数值v,当前的结果s
        System.out.println(dfs(0,0,0,1));
    }
    public static long dfs(int u,int k,int v,long s){
        if(u==N){
            if(k==K+1) return s;
            else return -1;
        }
        v=v*10+str.charAt(u)-'0';
        return Math.max(dfs(u+1,k,v,s),dfs(u+1,k+1,0,s*v));
    }
}

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while((t--)>0){
            int n=sc.nextInt();
            int[] w=new int[n+1];
            int f=-0x3f3f3f3f;
            int[] g=new int[n+2];
            int[] h=new int[n+2];
            g[0]=f;
            h[n+1]=f;
            for(int i=1;i<=n;i++){
                w[i]=sc.nextInt();
                f=Math.max(f+w[i],w[i]);
                g[i]=Math.max(f,g[i-1]);
            }
            f=-0x3f3f3f3f;
            for(int i=n;i>0;i--){
                f=Math.max(f+w[i],w[i]);
                h[i]=Math.max(f,h[i+1]);
            }
            int res=-0x3f3f3f3f;
            for(int i=1;i<n;i++){
                res=Math.max(res,g[i]+h[i+1]);
            }
            System.out.println(res);
        }
    }

}

二分
以开花的天数进行二分，然后找到对应天数能产生的花束的数量，若多于题意，可进一步缩小区间；少于，则区间扩大

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if(m*k>bloomDay.length) return -1;
        int max=0,min=0;
        for (int i : bloomDay) {
            max = Math.max(max, i);
        }
        while(min<max){
            int mid=(min+max)/2;
            int cnt=getCount(bloomDay,mid,k);
            if(cnt>=m) max=mid;
            else min=mid+1;
        }
        return min;
    }
    public int getCount(int[] bloomDay, int day, int k){
        int cnt=0,group=0;
        for(int i=0;i<bloomDay.length;i++){
            if(bloomDay[i]<=day)
                cnt++;
            else 
                cnt=0;

            if(cnt==k){
                group++;
                cnt=0;
            }
        }
        return group;
    }
}

import java.util.*;
class Main{
    static int cnt=0,len=0;
    static int index;
    static int N=65;
    static boolean[] vis=new boolean[N];
    static int[] sticks =new int[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        while(n!=0){
            index=0;
            int maxLen=0,sum=0;
            for(int i=0;i<n;i++){
                int val=sc.nextInt();
                if(val>50) continue;
                sticks[index]=val;
                sum+=sticks[index];
                maxLen=Math.max(maxLen,sticks[index]);
                index++;
            }
            Arrays.sort(sticks, 0, index);
            reverse(sticks,0,index-1);

            for(len=maxLen;len<=sum;len++){
                if(sum%len!=0) continue;
                cnt=sum/len;
                Arrays.fill(vis,false);
                if(dfs(1,0,0)){
                    System.out.println(len);
                    break;
                }
            }
            n=sc.nextInt();
        }
    }
    public static boolean dfs(int num,int curLen,int start){
        if(num>cnt) return true;
        if(curLen==len) return dfs(num+1,0,0);
        for(int i=start;i<index;i++){
            if(!vis[i]&&curLen+sticks[i]<=len){
                vis[i]=true;
                if(dfs(num,curLen+sticks[i],i+1))
                    return true;
                vis[i]=false;
                //以下为剪枝内容。否则会TLE
                //1.若sticks[i]放在其他地方会失败，那么其作为第一段或者最后一段也会失败
                if(curLen==0||curLen+sticks[i]==len) return false;
                //2.若存在相同长度的段，其一失败，另外的也肯定失败，无需再拼接
                int j=i;
                while(j<index&&sticks[j]==sticks[i]) j++;
                i=j-1;
            }
        }
        return false;
    }
    public static void reverse(int[] sticks,int s,int e){
        while(s<=e){
            int tmp=sticks[s];
            sticks[s]=sticks[e];
            sticks[e]=tmp;
            s++;
            e--;
        }
    }
}

import java.util.*;

class Main{
    static int N=12;
    static char[][] res=new char[N][N];
    static boolean[] st=new boolean[N];
    static boolean[] diag=new boolean[2*N];
    static boolean[] udiag=new boolean[2*N];
    static int n;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                res[i][j]='.';
        }
        dfs(0);

    }
    public static void dfs(int rows){
        if(rows==n){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++)
                    System.out.print(res[i][j]);
                System.out.println();
            }
            System.out.println();
            return;
        }
        for(int i=0;i<n;i++){
            if(!st[i]&&!diag[i-rows+n]&&!udiag[i+rows]){
                st[i]=diag[i-rows+n]=udiag[i+rows]=true;
                res[rows][i]='Q';
                dfs(rows+1);
                st[i]=diag[i-rows+n]=udiag[i+rows]=false;
                res[rows][i]='.';
            }
        }
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplication(ListNode head) {
        ListNode res=new ListNode(-1);
        res.next=head;
        ListNode s=res;

        while(s.next!=null){
            ListNode f=s.next;
            while(f!=null&&s.next.val==f.val) f=f.next;
            //判断s,f之间距离 如果是1则没有重复元素
            if(s.next.next==f) s=s.next;
            else s.next=f;

        }
        return res.next;
    }
}

思路参照：AcWing 92. 递归实现指数型枚举

思路

dfs(pos,sum):
pos表示a数组中当前用到的数的位置
sum表示当前用到了几个数

（1）排序，相同的数在同一段
（2）找到该段的首尾，对于该段的问题即为选该元素选多少个：0，1，2…，k个；选了该元素即置对于位置的标记状态为ture；最终输出选了元素个数为m的结果
（3）由于要求字典序排列，原数组是升序排列的，故含有相同元素的输出结果的顺序应该首先输出全选元素的结果，依次递减到不选该元素的结果。
举个栗子（包含2个重复元素2）：
1，2，2，3
1，2，3，4
递归dfs(k,sum);

代码

import java.util.*;
class Main{
    static int n,m;
    static int N=30;
    static int[] a=new int[N];
    static boolean[] st=new boolean[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        Arrays.sort(a,1,n+1);
        dfs(1,0);
    }
    /*
    pos表示a数组中当前用到的数的位置
    sum表示当前用到了几个数
    */
    public static void dfs(int pos,int sum){
        if(sum==m){
            for(int i=1;i<=n;i++){
                if(st[i])
                    System.out.print(a[i]+" ");
            }
            System.out.println();
            return;
        }
        if(sum>m) return;
        if(pos>n) return;//当前数组已经遍历完了
        //找相同数出现的段
        int k=pos;
        while(k<=n&&a[k]==a[pos]){//k是下一段的第一个数
            st[k]=true;
            k++;
            sum++;
        }
        dfs(k,sum);
        for(int i=k-1;i>=pos;i--){
            st[i]=false;//恢复，选择的元素递减
            sum--;
            dfs(k,sum);
        }
    }
}

朴素做法

定义一个last指针，该指针指向当前所选取元素的位置，下一次选取的元素必须在其后

import java.util.*;
class Main{
    static int n,m;
    static int N=30;
    static int[] a=new int[N];
    static boolean[] st=new boolean[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        a[0]=1;
        dfs(1,0);
    }
    public static void dfs(int pos,int last){
        if(pos>m){
            for(int i=1;i<=m;i++){
                System.out.print(a[i]+" ");
            }
            System.out.println();
            return;
        }

        for(int i=1;i<=n;i++){//第i个数后面的数不能小于其前面的数
            if(!st[i]&&i>last){
                st[i]=true;
                a[pos]=i;
                dfs(pos+1,i); 
                st[i]=false;
            }
        }
    }
}

特例

这题因为是从1-n，排序，所以取上一个位置所放的元素值，也是该元素所出现的位置。所以可以从a[pos-1]开始遍历

import java.util.*;
class Main{
    static int n,m;
    static int N=30;
    static int[] a=new int[N];
    static boolean[] st=new boolean[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        a[0]=1;
        dfs(1);
    }
    public static void dfs(int pos){
        if(pos>m){
            for(int i=1;i<=m;i++){
                System.out.print(a[i]+" ");
            }
            System.out.println();
            return;
        }

        for(int i=a[pos-1];i<=n;i++){//第i个数后面的数不能小于其前面的数
            if(!st[i]){
                st[i]=true;
                a[pos]=i;
                dfs(pos+1); 
                st[i]=false;
            }
        }
    }
}

对比题目https://www.acwing.com/activity/content/code/content/328714/
这题重复元素的选择方案在于选多少个

import java.util.*;
class Main{
    static int n;
    static int N=20;
    static int[] a=new int[N];
    static boolean[] st=new boolean[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        Arrays.sort(a,1,n+1);
        dfs(1);
    }
    public static void dfs(int pos){
        if(pos>n){
            for(int i=1;i<=n;i++){
                if(st[i]){
                    System.out.print(a[i]+" ");
                }
            }
            System.out.println();
            return;
        }

        int tmp=pos;
        while(a[pos]==a[tmp]) tmp++;//tmp最终指向和其不等区间的第一个
        dfs(tmp);//重复元素选0个
        //表示重复元素选多少个
        for(int i=pos;i<tmp;i++){
            st[i]=true;
            dfs(tmp);
        }
        //恢复现场，对所有重复元素还原
        for(int i=pos;i<tmp;i++) st[i]=false;
    }
}