算法是抽象的概念，但越是抽象的東西，其越具有清晰的特征。特征如下：
確定性：?算法的每一個步驟都是明確的、可行的、結果可預期的
有窮性：?算法要有一個終止條件
輸入和輸出：?算法是用來解決問題的，少不了輸入和輸出
算法設計
這一塊兒其實是很龐大的知識體系，需要苦練內功根基。下面簡要介紹下算法設計方面的知識。
順序執(zhí)行、循環(huán)和分支跳轉是程序設計的三大基本結構。
算法也是程序，千姿百態(tài)的算法也是由這三大基礎結構構成的。
算法和數(shù)據(jù)結構關系緊密，數(shù)據(jù)結構是算法設計的基礎。
如果對諸如哈希表、隊列、樹、圖等數(shù)據(jù)結構有深刻的認識，那在算法設計上將會事半功倍。
上面提到的知識，主要的目的是拋磚引玉。算法的設計與分析是無上神功的心法口訣和入門要領。無論多么精妙絕倫的算法實現(xiàn)，都是由一些最基礎的模型和范式組裝起來的。
關于算法設計，這里給大家推薦一門課程，很不錯，小伙伴可以看看：
算法設計與分析-Design and Analysis of Algorithms
降維分析，化繁為簡
現(xiàn)在，到了最關鍵的時刻。我們回到題目中，開始設計我們的算法。
題干信息很簡單，核心問題在于：
如何從數(shù)組中選取?N?個數(shù)進行求和運算。
如何做，這里我們通常且正確的做法，是對問題進行降維分析，并且化繁為簡。
下面開始降維分析，化繁為簡：
假如?N = 2?，也就是找出數(shù)組中兩個數(shù)的和為?M?的話，你會怎么做？可能你會想到每次從數(shù)組中彈出一個數(shù)，然后與余下的每個數(shù)進行相加，最后做判斷。
那么問題來了，當??N = 3?呢，N = 10?呢，會發(fā)現(xiàn)運算量越來越大，之前的方式已經不可行了。
不妨換一種思路：
數(shù)組中選取不固定數(shù)值?N?，我們可以嘗試著使用標記的方式，我們把?1?表示成選取狀態(tài)， 把?0?表示成未選取狀態(tài)。
假設數(shù)組?constarr=[1,2,3,4]?，對應著每個元素都有標記?0?或者?1?。如果?N=4?，也就是在這個數(shù)組中，需要選擇?4?個元素，那么對應的標記就只有一種可能?1111?，如果?N=3?，那就有?4?種可能，分別是?1110?、?1101?、1011以及?0111?(也就是?C4取3->4?) 種可能。
開始抽象
通過上面的層層敘述，我們現(xiàn)在的問題可以抽象為：
標記中有幾個?1?就是代表選取了幾個數(shù)，然后再去遍歷這些?1?所有可能存在的排列方式，最后做一個判斷，這個判斷就是：每一種排列方式，都代表著數(shù)組中不同位置的被選中的數(shù)的組合，所以這里就是將選中的這些數(shù)字，進行求和運算，然后判斷求出的和是不是等于?M?。
于是，問題開始變得簡單了。
如何將數(shù)組和標記關聯(lián)
0101?這樣的數(shù)據(jù)一眼望上去第一反應就是二進制啊
對于?arr?來說，有 4 個元素，對應的選擇方式就是從?0000（?N = 0?）到?1111(?N = 4?)的所有可能。
而?1111?就是?15?的二進制，也就是說這所有的可能其實對應的就是?0 - 15?中所有數(shù)對應的二進制。
這里的問題最終變成了如何從數(shù)組長度?4?推導出?0 - 15
這里采用了位運算--左移運算，?1 << 4?的結果是?16?。
java實現(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個數(shù)之和等于m的，n個數(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');
? ? }
