[Question]
  [
We define a *binarray* as an array satisfying the following properties:
* it's non-empty
* the first value is a `1`
* the last value is a `1`
* all other values are either `0` or `1`
For instance, the array `[ 1, 1, 0, 1 ]` is a valid *binarray*.
## The task
Given a non-empty array **A** of non-negative integers and a positive integer **N**, your job is to find a *binarray* **B** of length **N** which allows to generate **A** by summing an unrestricted number of copies of **B**, shifted by an unrestricted number of positions.
### Example
```
A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
N = 4
```
For this input, the *binarray* `B = [ 1, 1, 0, 1 ]` would be a valid answer because we can do:
```
  [ 1, 1, 0, 1 ]
+       [ 1, 1, 0, 1 ]
+       [ 1, 1, 0, 1 ]
+          [ 1, 1, 0, 1 ]
+                   [ 1, 1, 0, 1 ]
+                                  [ 1, 1, 0, 1 ]
  -----------------------------------------------
= [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
```
### Rules
* Input can be taken in any reasonable format.
* Output can be either a native array (e.g. `[1, 1, 0, 1]`) or a binary string with or without a separator (e.g. `"1,1,0,1"` or `"1101"`)
* You're only required to print or return one valid *binarray*. Alternatively, you may choose to print or return *all of them* when several solutions exist.
* You are not required to support inputs that do not lead to any solution.
* The sum may include implicit zeros which do not overlap with any copy of **B**. The second zero in the above sum is such an implicit zero.
* Your can assume that the maximum size of **A** is 100 and the maximum size of **B** is 30.
* This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.
## Test cases
```
Input : N = 1 / A = [ 1, 2, 3, 4, 5 ]
Output: [ 1 ]
Input : N = 2 / A = [ 1, 2, 100, 99 ]
Output: [ 1, 1 ]
Input : N = 3 / A = [ 1, 1, 1 ]
Output: [ 1, 1, 1 ]
Input : N = 3 / A = [ 1, 1, 3, 2, 2 ]
Output: [ 1, 1, 1 ]
Input : N = 3 / A = [ 1, 0, 2, 1, 1, 1, 0, 0, 1, 0, 1 ]
Output: [ 1, 0, 1 ]
Input : N = 4 / A = [ 1, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1 ]
Input : N = 4 / A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1 ]
Input : N = 4 / A = [ 1, 1, 0, 2, 1, 0, 1 ]
Output: [ 1, 0, 0, 1 ] or [ 1, 1, 0, 1 ]
Input : N = 5 / A = [ 1, 3, 6, 9, 8, 6, 3, 4 ]
Output: [ 1, 1, 1, 0, 1 ]
Input : N = 8 / A = [ 2, 1, 0, 2, 3, 3, 1, 2, 1 ]
Output: [ 1, 0, 0, 1, 1, 1, 0, 1 ]
Input : N = 10 / A = [ 1, 2, 1, 2, 2, 1, 3, 3, 3, 2, 3, 0, 2, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 ]
Input : N = 13 / A = [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 ]
Output: [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]
Input : N = 5 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1, 1 ]
Input : N = 6 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 0, 0, 0, 1 ]
Input : N = 7 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 0, 0, 0, 1, 1 ]
Input : N = 9 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 1, 0, 1, 0, 1, 0, 1 ]
```
  
[Answer]
# PHP, ~~105 92 90~~ 86 bytes
[Jörg´s solution](https://codegolf.stackexchange.com/a/114493) fixed and golfed:
```
for($b=1+2**$argv[1];;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));
```
takes `N` from first command line argument, values after that;
run with `-r`or [test it online](http://sandbox.onlinephpfunctions.com/code/8324bb7e85c80de294c1b07785c69ce92cb939eb).  
prints binary number (format `10001`);
prints invalid solution or runs dead if there is no valid solution.
**first version** (now 97 bytes) that prints nothing for invalid input: [test it online](http://sandbox.onlinephpfunctions.com/code/0de45729a20b4528fe7a241b074dec23f5f231c9)
```
for($b=1+$m=2**$argv[1];$m/2<=$b;)--$argc>1?$s+=$argv[$argc]*2**$i++:$s%($b-=2)||die(decbin($b));
```
**breakdown**
```
for($b=1+$m=2**$argv[1];$m/2<=$b;)  # second loop: loop $b from 2^N-1 by -2 to 2^(N-1)
--$argc>1                           # first loop: decrease $argc ...
    ?$s+=$argv[$argc]*2**$i++           # while $argc>1: binary sum from last to 2nd argument
    :$s%($b-=2)||die(decbin($b));       # later: if $b divides $s, print in binary and exit
```
[Answer]
# [PHP](https://php.net/), 219 bytes
```
<?for(list($g,$z)=$_GET,$d=~-$l=2**$z;$d>=$l/2;max(array_diff_assoc($r,$g)?:[0])?:$o[]=$b,$d-=2)for($r=[],$b=decbin($d),$k=0;$k<count($g);$k++)for($u=$g[$k]-$r[$k],$i=0;$i<$z;$i++)$u<1?:$r[$k+$i]+=$u*$b[$i];print_r($o);
```
[Try it online!](https://tio.run/##hVRNj9owEL3zK1A6hwSMajuwuzSke6hWVS/tZW9eKwoQIIUmkQNVu1X3r1N/xIkJqy0jTBi/efNmPE61q86L@2pXDTIhSpGIrCrFMS@2/stD8vXb45dPD0E02JQiS1c7nw0YI4iiEE3RjCOCGOF8gIyTYIzmcy6fGGnd0riES4/jCiWG9t1YUWjD0tTaRGInhzLpnupIh5FKl9knNthSaCx2sNii2j0l3dGhiLBRPtX5LWD4TmQ/M1FnBhmiGzRHd3KV/eBopkVZItpkCqURo/pOkWFCLiqyqkNtCm8boRUSbCRehpnylMqwSRG2RLQNMzGYuMqH7bHoNl9ac1xEd7379PrvGrFlk7dBNw3j26hbXSvG/yGb69qMudNjvldT09X66jias6bNWV8dsz1H4gCUf6YZZz2vEaHX3s7VTLY7YaNPXaquVZ3AqZ4JFR2aXXLZSDMKdiBw10jyCsxeEHJBNbTasdNIbKq4tcPQ4zLvAWrvih3wZlbdq@miSQ9tLoRE87SG5PPDY/DnVNTZ0YcyiM7yveMf8lr@2yJ4DmKNQLCOXyZwiOloBM8RrD/GcHhPox/pLz8VIv2drPPNJknrulz5IBBsg/sPDHO5Qsl4DEvJMIlpoNhBxIwjWMbrbLXMCx/WAYJ9jCPYL1blqVCpA/lnPDbwUwxbBns@AaF@EOQKmy@UkFyC4LQgMo/aHEPOxzGcRrBk8jGqRF4cE2Eqy1a7cvi9lBk95CHpQt7T0UOdR1XKKG/83lPhRYO/538 "PHP – Try It Online")
-4 Bytes using `[$g,$z]=$_GET` PHP 7.1 instead of `list($g,$z)=$_GET`
[Answer]
# Python, 166 bytes
```
def f(a,n):
 for i in range(1<<n-1,1<<n):
  b=bin(i)[2:];u,v=(int(('0{:0>%d}'%sum(a)*len(s)).format(*s))for s in[a,b])
  if u%v<1>int(str(u//v*10)[::~sum(a)]):yield b
```
[Try it online!](https://tio.run/##nZJda4MwFIbv@yvOjTQp2ZqPtqvO9o@IF4q6BWxa/IIytr/uEp1OqGmh8KKBvOc5OW9yuVafZyXaNkkzyFBEFPYWkJ0LkCAVFJH6SBHzffXCiPmZXYgPsVRI4oB74XtNmgOSqkJoSb88enSS76VT1icU4VWeKlRi/Kp5p6hCK7026FKjg4jEIdYwmUHtND47GkZZFaher5sVozjwvJ@eE2LvKtM8gbi9FMaWy7JCGQoYAU5AENgQ2IYEGMZ4MWdhlBJwXW3hsxYjvSlsm6KjcKuF9l0G0U79ws7lg4xlY2vNu@lGO5uipz2sADqtsxr1hDsdEYF9tzCZau/21ssnUNGJjUPsrflPji8G9YBpdH8n1Jdvu6Qh21n9XyR7kPit2Py0j4t2zxS9PVPk3nl64/fuM2azYRl7@ws "Python 3 – Try It Online")
### How it works
Consider A and B as the digits of base *k* numbers *u* and *v*. For example (we’ll use *k* = 1000 for illustration):
A = [1, 2, 1, 3, 2, 1, 2]  
B = [1, 0, 0, 1]  
*u* = 1 002 001 003 002 001 002  
*v* = 1 000 000 001
As many of the other answerers noticed, if B is a valid answer, then *u* is divisible by *v*. In this case,
*u* = 1 002 001 002 ⋅ *v*
This quotient, translated back to the array [1, 2, 1, 2], tells us exactly how many copies of B we need shifted to each position.
```
  [1, 0, 0, 1]
+    [1, 0, 0, 1]
+    [1, 0, 0, 1]
+       [1, 0, 0, 1]
+          [1, 0, 0, 1]
+          [1, 0, 0, 1]
-----------------------
  [1, 2, 1, 3, 2, 1, 2]
```
(Why? Because that is exactly how long multiplication works in base *k*.)
What the other answerers failed to notice is that **the above condition is not sufficient**. For example:
A = [1, 2, 1, 3, 2, 1, 2]  
B = [1, 1, 1, 1]  
*u* = 1 002 001 003 002 001 002  
*v* = 1 001 001 001  
*u* = 1 000 999 002 ⋅ *v*
Mathematically speaking, we can still translate that quotient back to the array [1, 1, −1, 2], which works fine if we’re allowed to use negative copies of B:
```
  [1, 1, 1, 1]
+    [1, 1, 1, 1]
−       [1, 1, 1, 1]
+          [1, 1, 1, 1]
+          [1, 1, 1, 1]
-----------------------
  [1, 2, 1, 3, 2, 1, 2]
```
but of course the challenge does not permit negative copies. So we need an additional check.
Toward that end, we select a base *k* = 10*e* where *k* > 10 ⋅ sum(A), and check that none of the base *k* digits overflow into the next base *k* digit when we multiply the quotient by ten. That is, every *e*th base ten digit, starting at the end, in the base ten representation of the quotient times ten, must be 0. This guarantees that the quotient translates back to an array with nonnegative elements.
[Answer]
# PHP, 213 Bytes
Same way a little bit golfed
```
<?for($b=2**~-$l=$_GET[1];$b<2**$l;array_filter($t[$b++])?:$d[]=$o)for($g=count($t[$b]=$_GET[$i=0]);min($t[$b])>-1&$i<=$g-$l;$i++)for($e=$t[$b][$i],$k=0,$o=decbin($b);$k<$l;)$t[$b][$k+$i]-=$o[$k++]*$e;print_r($d);
```
[Try it online!](https://tio.run/##fVJdb4IwFH33VyzmZrFSkxbUyUrn07I/sDfWGPlQiA4I4sOybH/dXVo60S1yQtOce@53q6w6Bcsqqwabsk7XcTYKB2HIqUs9OqUzRTkNuVIDakjOGPV9hbeQ/9IIhXJkepSHGveaZm0IDYZoz86T9XK0QHqqPXsRXaSMnVtnG0JrWU/LrMrYGEOyJ/DonPp0gSd2qehMp7Jmt/P3ENzUsjAx@EWdthZPo9Xb9nRezkxRl26290t0M@R6FOfvaih9cFs1vy2adxFvqx50qW2HN2W@3pRBf6Xm/7PKc6//vBE75fOGkFfrA6xenl/J57E4pM0IEiJO@DBHEEl3PP6ewF5qAb5JAVGAHOzFuq7XH6tNvm9SVDYhRI6jyPIRklBJKIkOsJVxeSwaY1ddFMglU0S850XHk6cJv4c8kLDFXAJyxzHuqTQCdFEUdpJRKGWSxlHrGhEBuwD1xIp2DuommLy9OmoMqajqvGhWtekpjbPyztTgKikhocO3Yii@Tj8 "PHP – Try It Online")
## PHP, 344 Bytes first working
After my first answer I have decide to make a longer try that give back all valid solutions.
```
<?foreach(range(2**($l=$_GET[1])-1,2**($l-1))as$b){$t[$b]=($g=$_GET[0]);for($i=0;$t[$b]&&$i<=count($g)-$l;$i++){$e=reset($y=array_slice($t[$b],$i,$l));foreach(str_split(decbin($b))as$k=>$v)$t[$b][$k+$i]=$y[$k]-$e*$v;if(min($t[$b])<0)unset($t[$b]);}}foreach($t as$k=>$v)if(max($v)>0)unset($t[$k]);echo join(",",array_map(decbin,array_keys($t)));
```
[Online Version](http://sandbox.onlinephpfunctions.com/code/07f41c350db36f3709a13fd3c4c71c8e23e0aa5c)
## Breakdown
```
foreach(
    range(2**($l=$_GET[1])-1
    ,2**($l-1)
    ) # make decimal range of a binarray with given length
    as$b){
$t[$b]=($g=$_GET[0]); # make a copy for each possible solution pattern
    for($i=0;$t[$b]&&$i<=count($g)-$l;$i++){ # Loop till solution is valid or reach last digit
        $e=reset($y=array_slice($t[$b],$i,$l)); # take first value of a sequence with the length
        foreach(str_split(decbin($b))as$k=>$v)
            $t[$b][$k+$i]=$y[$k]-$e*$v; # replace values in copy
        if(min($t[$b])<0)unset($t[$b]); # kill solution if a minimum <0 exists
    }
}
foreach($t as$k=>$v)if(max($v)>0)unset($t[$k]); # drop all solutions where the sum is not zero 
echo join(",",array_map(decbin,array_keys($t))); #Output all solutions
```
[Answer]
## Python, 205 bytes
```
def f(a,l):
 b=lambda s:b(s[:-1])*sum(a)*8+int(s[-1])if s else 0
 c=lambda n:n and(n/sum(a)/4%2 or c(n/sum(a)/8))
 for i in range(2**~-l,2**l):
  j=bin(i)[2:]
  if b(a)%b(j)<1 and not c(b(a)/b(j)):return j
```
Returns a binary string without separator. As @AndersKaseorg points out, there are inputs for which @fəˈnɛtɪk's solution doesn't work because the division represents a negative coefficient which is disallowed. To work around this, I use a very large base and test that there is no borrow in the division.
[Answer]
# Pyth, 32 bytes
```
f!|%FKiRJysQ,QT>#sQj/FKJ+L1^U2tE
```
[Try it online](https://pyth.herokuapp.com/?code=f%21%7C%25FKiRJysQ%2CQT%3E%23sQj%2FFKJ%2BL1%5EU2tE&input=%5B1%2C+1%2C+2%2C+4%2C+1%2C+2%2C+2%2C+1%2C+0%2C+1%2C+0%2C+1%2C+1%2C+0%2C+1%5D%0A4)
### How it works
```
                           ^U2tE   Cartesian power [0, 1]^(N - 1)
                        +L1        prepend 1 to every list
f                                  filter for lists T such that:
          sQ                         sum(A)
         y                           double
        J                            assign to J
      iR    ,QT                      convert [A, T] from base J
     K                               assign to K
   %F                                fold modulo
  |                                  logical OR with
                    /FK                fold integer division over K
                   j   J               convert to base J
               >#sQ                    filter for digits greater than sum(A)
 !                                   logical NOT
```
The strategy is similar to my [Python answer](https://codegolf.stackexchange.com/a/124462), except that since Pyth has builtins for base conversion, we can use a more efficient base *k* = 2 ⋅ sum(A), and check directly that every digit of the quotient is at most sum(A).
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), ~~77~~ ~~74~~ ~~96~~ 80 bytes
```
n->a->[v|d<-divisors(b=Pol(a)),(v=Vec(d))%2==v&&vecmin(Vec(b/d))>=0&&d%x&&#d==n]
```
Returns all solutions.
First converts the array `a` to a polynomial `b`. Then chooses from the divisors `b` the polynomials `d` such that the coefficients of `d` are all `1` and `0`, and the coefficients of `b / d` are all nonnegative, and `d(0) = 1`, and `deg(d) = n + 1`. Finally, converts them back to arrays.
[Try it online!](https://tio.run/##lVLdasMgGL3fU3wwKgqG@ZN0DdQ8w652U3qR1nYIWxrSIrvYu2eJaRZd3CBwEPH88Hm0LhuTvNXtGRS0VVKUSbGzX3qbaGPN9dJc8UG9XN5xSQjFVr2ejlgTshJKWYTs6fhhKtwfHp6640IxhPTqE6FHrVS1b@vGVDd8xpzgHXAKgoKkkFLIYE/Iw0iLieaMUcjzgJZ3usdfhHRuEaXZkDyCOQybMC@d5hgQpwdFSicp9yP/z/bnmYmyu6i7zbqrgcLGbfrOAt2m1wkvTDrwyNCceeV688oRg9vvaDYW919gLDCK2Ctlv1udIzSslxqelxrypYbwK/2sTtR@Aw "Pari/GP – Try It Online")
]