算法是抽象的概念蝗罗，但越是抽象的東西躁锁，其越具有清晰的特征拄显。特征如下：
確定性：?算法的每一個(gè)步驟都是明確的裁蚁、可行的矢渊、結(jié)果可預(yù)期的
有窮性：?算法要有一個(gè)終止條件
輸入和輸出：?算法是用來(lái)解決問題的，少不了輸入和輸出
算法設(shè)計(jì)
這一塊兒其實(shí)是很龐大的知識(shí)體系枉证，需要苦練內(nèi)功根基矮男。下面簡(jiǎn)要介紹下算法設(shè)計(jì)方面的知識(shí)。
順序執(zhí)行室谚、循環(huán)和分支跳轉(zhuǎn)是程序設(shè)計(jì)的三大基本結(jié)構(gòu)毡鉴。
算法也是程序崔泵，千姿百態(tài)的算法也是由這三大基礎(chǔ)結(jié)構(gòu)構(gòu)成的。
算法和數(shù)據(jù)結(jié)構(gòu)關(guān)系緊密猪瞬，數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計(jì)的基礎(chǔ)管削。
如果對(duì)諸如哈希表、隊(duì)列撑螺、樹含思、圖等數(shù)據(jù)結(jié)構(gòu)有深刻的認(rèn)識(shí)，那在算法設(shè)計(jì)上將會(huì)事半功倍甘晤。
上面提到的知識(shí)含潘，主要的目的是拋磚引玉。算法的設(shè)計(jì)與分析是無(wú)上神功的心法口訣和入門要領(lǐng)线婚。無(wú)論多么精妙絕倫的算法實(shí)現(xiàn)遏弱，都是由一些最基礎(chǔ)的模型和范式組裝起來(lái)的。
關(guān)于算法設(shè)計(jì)塞弊，這里給大家推薦一門課程漱逸，很不錯(cuò)，小伙伴可以看看：
算法設(shè)計(jì)與分析-Design and Analysis of Algorithms
降維分析游沿，化繁為簡(jiǎn)
現(xiàn)在饰抒，到了最關(guān)鍵的時(shí)刻。我們回到題目中诀黍，開始設(shè)計(jì)我們的算法袋坑。
題干信息很簡(jiǎn)單，核心問題在于：
如何從數(shù)組中選取?N?個(gè)數(shù)進(jìn)行求和運(yùn)算眯勾。
如何做枣宫，這里我們通常且正確的做法，是對(duì)問題進(jìn)行降維分析吃环，并且化繁為簡(jiǎn)也颤。
下面開始降維分析，化繁為簡(jiǎn)：
假如?N = 2?郁轻，也就是找出數(shù)組中兩個(gè)數(shù)的和為?M?的話翅娶，你會(huì)怎么做？可能你會(huì)想到每次從數(shù)組中彈出一個(gè)數(shù)范咨，然后與余下的每個(gè)數(shù)進(jìn)行相加故觅，最后做判斷厂庇。
那么問題來(lái)了渠啊，當(dāng)??N = 3?呢，N = 10?呢权旷，會(huì)發(fā)現(xiàn)運(yùn)算量越來(lái)越大替蛉，之前的方式已經(jīng)不可行了贯溅。
不妨換一種思路：
數(shù)組中選取不固定數(shù)值?N?，我們可以嘗試著使用標(biāo)記的方式躲查，我們把?1?表示成選取狀態(tài)它浅， 把?0?表示成未選取狀態(tài)。
假設(shè)數(shù)組?constarr=[1,2,3,4]?镣煮，對(duì)應(yīng)著每個(gè)元素都有標(biāo)記?0?或者?1?姐霍。如果?N=4?，也就是在這個(gè)數(shù)組中典唇，需要選擇?4?個(gè)元素镊折，那么對(duì)應(yīng)的標(biāo)記就只有一種可能?1111?，如果?N=3?介衔，那就有?4?種可能恨胚，分別是?1110?、?1101?炎咖、1011以及?0111?(也就是?C4取3->4?) 種可能赃泡。
開始抽象
通過上面的層層敘述，我們現(xiàn)在的問題可以抽象為：
標(biāo)記中有幾個(gè)?1?就是代表選取了幾個(gè)數(shù)乘盼，然后再去遍歷這些?1?所有可能存在的排列方式升熊，最后做一個(gè)判斷，這個(gè)判斷就是：每一種排列方式绸栅，都代表著數(shù)組中不同位置的被選中的數(shù)的組合僚碎，所以這里就是將選中的這些數(shù)字，進(jìn)行求和運(yùn)算阴幌，然后判斷求出的和是不是等于?M?勺阐。
于是，問題開始變得簡(jiǎn)單了矛双。
如何將數(shù)組和標(biāo)記關(guān)聯(lián)
0101?這樣的數(shù)據(jù)一眼望上去第一反應(yīng)就是二進(jìn)制啊
對(duì)于?arr?來(lái)說(shuō)渊抽，有 4 個(gè)元素，對(duì)應(yīng)的選擇方式就是從?0000（?N = 0?）到?1111(?N = 4?)的所有可能议忽。
而?1111?就是?15?的二進(jìn)制懒闷，也就是說(shuō)這所有的可能其實(shí)對(duì)應(yīng)的就是?0 - 15?中所有數(shù)對(duì)應(yīng)的二進(jìn)制。
這里的問題最終變成了如何從數(shù)組長(zhǎng)度?4?推導(dǎo)出?0 - 15
這里采用了位運(yùn)算--左移運(yùn)算栈幸，?1 << 4?的結(jié)果是?16?愤估。
java實(shí)現(xiàn)方法如下：
import org.apache.commons.lang3.StringUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
/**
* @author zhengjimin
* @date 2021/2/26 下午2:46
* @function 整形數(shù)組，n速址、m
* 滿足n個(gè)數(shù)之和等于m的玩焰，n個(gè)數(shù)的所有組合
*/
public class ArithTest {
? ? @Test
? ? public void test1(){
? ? ? ? int[] arg = {1,2,3,4,5,6,7,8,9};
? ? ? ? int n = 3;
? ? ? ? int m = 12;
? ? ? ? int size = arg.length;
? ? ? ? List<String> listBinary = storeBinary(size);
? ? ? ? List<int[]> list = new ArrayList<>();
? ? ? ? List<String> sizeEqualN = listBinary.stream()
? ? ? ? ? ? ? ? .filter(param->countN(param,n))
? ? ? ? ? ? ? ? .collect(Collectors.toList());
? ? ? ? sizeEqualN.stream()
? ? ? ? ? ? ? ? .forEach(binary->{
? ? ? ? ? ? ? ? ? ? int[] res = equalM(arg,binary,m);
? ? ? ? ? ? ? ? ? ? if (res != null){
? ? ? ? ? ? ? ? ? ? ? ? list.add(res);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? });
? ? }
? ? @Test
? ? public void test(){
? ? ? ? int[] arg = {1,2,3,4,5};
? ? ? ? int sum = Arrays.stream(arg).sum();
? ? ? ? System.out.println(sum);
? ? ? ? List<Integer> list = Arrays.stream(arg).boxed().collect(Collectors.toList());
? ? ? ? long count = list.stream().count();
? ? ? ? System.out.println(count);
? ? }
? ? private int[] equalM(int[] arg,String binary,int m){
? ? ? ? int sum = 0;
? ? ? ? List<Integer> list = new ArrayList<>();
? ? ? ? for (int i = 0; i < binary.length(); i++) {
? ? ? ? ? ? if (binary.charAt(i) == '1'){
? ? ? ? ? ? ? ? sum += arg[i];
? ? ? ? ? ? ? ? list.add(arg[i]);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if (sum == m){
? ? ? ? ? ? System.out.println(list);
? ? ? ? ? ? Integer[] toArray = list.toArray(new Integer[list.size()]);
? ? ? ? ? ? return list.stream().mapToInt(Integer::intValue).toArray();
? ? ? ? }
? ? ? ? return null;
? ? }
? ? private boolean countN(String param,int n){
? ? ? ? String rep = param.replaceAll("1","");
? ? ? ? if (param.length() - rep.length() == n){
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? return false;
? ? }
? ? private List<String> storeBinary(int size){
? ? ? ? List<String> listBinary = new ArrayList<>();
? ? ? ? int count = 1<<size;
? ? ? ? for (int i = 0; i < count; i++) {
? ? ? ? ? ? String binary = pad0Right(i,size);
? ? ? ? ? ? listBinary.add(binary);
? ? ? ? }
? ? ? ? return listBinary;
? ? }
? ? private String pad0Right(int i,int size){
? ? ? ? String param = Integer.toBinaryString(i);
? ? ? ? return StringUtils.leftPad(param,size,'0');
? ? }
